Baekjoon 1495번 기타리스트

문제

https://www.acmicpc.net/problem/1495

걸린 시간

-

풀이

JavaScript

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input';
const stdin = fs.readFileSync(filePath).toString().trim().split('\n').map(s => s.trim());
const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

const [N, S, M] = input().split(' ').map(Number);
const V = input().split(' ').map(Number);
const dp = Array.from(Array(N+1), () => Array(M+1).fill(0));

dp[0][S] = 1;
for(let i = 1; i < N+1; i++){
  for(let v = 0; v <= M; v++){
    if(dp[i-1][v]){
      if(v-V[i-1] >= 0) dp[i][v-V[i-1]] = 1;
      if(v+V[i-1] <= M) dp[i][v+V[i-1]] = 1;
    }
  }
}

let ans = -1;
for(let v = 0; v <= M; v++){
  if(dp[N][v]) ans = Math.max(ans, v);
}
console.log(ans);

매 단계마다 볼륨을 줄이거나 늘릴 수 있기 때문에 2가지의 선택을 할 수 있다.

먼저 작은 예제로 2의 n제곱 크기의 모든 경우의 수를 표시해보았다.

top-down 풀이는 현재 곡 i 과 볼륨 v 에서의 최대 볼륨을 메모이제이션 하면 되겠다는 생각이 바로 들었지만 bottom-up 풀이는 직관적으로 떠오르지 않았다.

그래서 top-down 에서 메모이제이션을 위해 필요한 값 i 와 v 를 가지고 bottom-up 으로 변경해보기로 했다.

현재 곡의 인덱스를 row, 볼륨을 col 로 하는 2차원 배열을 만들어두고 고민을 해 보았는데 생각보다 쉽게 아이디어를 찾을 수 있었고, dp 배열의 값은 조절 가능한 볼륨의 존재 여부로 정했다.

1. 먼저 시작 볼륨에 표시를 한다. (bottom-up 풀이므로 초기값 설정을 해 준다.)
2. 첫 번째 곡 부터 마지막 곡 까지 이전에 존재하는 모든 볼륨에서 V[i] 값을 빼거나 줄인 볼륨을 dp 배열에 표시한다. (단, 0 보다 크거나 같고 M 보다 작거나 은 범위 내에서만)
3. 마지막 곡에 표시된 볼륨 중 제일 큰 볼륨을 정답으로 출력한다. 만약 조절 가능한 볼륨이 없다면 -1 를 출력한다.

다른 풀이

JavaScript

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input';
const stdin = fs.readFileSync(filePath).toString().trim().split('\n').map(s => s.trim());
const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

const [N, S, M] = input().split(' ').map(Number);
const V = input().split(' ').map(Number);
const dp = Array.from(Array(N+1), () => Array(M+1).fill(Number.NEGATIVE_INFINITY));

const solve = (i, v) => {
  // 기저 사례
  if(i === N) return v;
  // 메모이제이션
  if(dp[i][v] !== Number.NEGATIVE_INFINITY) return dp[i][v];
  // 재귀 호출
  let ret = -1;
  if(v-V[i] >= 0) ret = Math.max(ret, solve(i+1, v-V[i]));
  if(v+V[i] <= M) ret = Math.max(ret, solve(i+1, v+V[i]));
  return dp[i][v] = ret;
}

console.log(solve(0, S));

top-down 풀이다.