[JS][백준]1495_기타리스트

문제 번호

1495번: 기타리스트

 

 

알고리즘 분류

• 다이나믹 프로그래밍

 

문제 풀이

 처음엔 DFS, BFS를 생각했다. 그러나 시간 초과와, 메모리 초과에 직면했다.

그래서 2차원 배열을 사용해야 한다는 것을 알았다.

세로축을 노래, 가로축을 볼륨으로 생각하자.

   let dp = new Array(51).fill(null).map(_ => new Array(1001).fill(false));

 이제 주어진 노래만큼 탐색하면서 해당 노래를 시작할 때 해당 볼륨이 가능하면 true, 불가능하다면 false로 2차원 배열을 채워 나갈 것이다. 예를 들어 5번째 노래를 시작할 때 볼륨 10이 가능하다면 DP[5][10]은 true 값을 갖는다.

0번째 노래는 없음으로 처음 시작볼륨S를 생각하여 dp[0][S]는 true이다.

 

이전 노래의 볼륨에서 현재 노래를 시작하기 전에 볼륨을 +- 해보아서 해당 볼륨으로 노래를 시작할 수 있는지 확인해보자.

   for (let i = 1; i <= N; i++) {
      for (let j = 0; j <= M; j++) {
         if (!dp[i - 1][j]) {
            continue;
         }
         if (j - V[i - 1] >= 0) {
            dp[i][j - V[i - 1]] = true;
         }
         if (j + V[i - 1] <= M) {
            dp[i][j + V[i - 1]] = true;
         }
      }
   }

 

마지막으로 N번째 노래에서 가장 큰 볼륨을 찾아야 하므로 DP[N] 중에서 가장 큰 값을 갖는 true 값을 찾아보자.

   for (let i = 0; i <= M; i++) {
      if (dp[N][i]) {
         if (i > answer)
            answer = i;
      }
   }

 

전체 코드

function main() {
   let answer = -1;

   const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n');
   const [N, S, M] = input[0].split(' ').map(Number);
   let V = input[1].split(' ').map(Number);

   answer = BFS(0, N, S, M, V)

   return console.log(answer);
}
function BFS(idx, N, S, M, V) {  // 인덱서, 노래수, 시작볼륨, 최대볼륨, 볼륨리스트.
   let answer = -1;

   let dp = new Array(51).fill(null).map(_ => new Array(1001).fill(false));
   dp[0][S] = true;

   for (let i = 1; i <= N; i++) {
      for (let j = 0; j <= M; j++) {
         if (!dp[i - 1][j]) {
            continue;
         }
         if (j - V[i - 1] >= 0) {
            dp[i][j - V[i - 1]] = true;
         }
         if (j + V[i - 1] <= M) {
            dp[i][j + V[i - 1]] = true;
         }
      }
   }
   for (let i = 0; i <= M; i++) {
      if (dp[N][i]) {
         if (i > answer)
            answer = i;
      }
   }

   return answer;
}
main();

특이사항

 처음에는 DFS나 2차원 배열이나 뭐가 다른지 감이 안 왔다. 그런데 DFS로 탐색을 하게 되면 중복된 값에 대해서 여러 번 계산하는 경우가 생긴다. 가령 5번째 노래쯤에 볼륨 10을 갖는 경우가 1가지 경우가 아니라 여러번 있을 수 있다는 것이다. 그래서 필요 없는 연산이 많아져서 시간 초과에 걸리게 된다. 반면 2차원 배열을 사용하면 중복되는 연산들을 피할 수 있으므로 최대 2차원 배열의 크기만큼만 계산하면 되므로 시간 초과를 피할 수 있다.