[JS][백준]17845_수강 과목

문제 번호

17845번: 수강 과목

 

 

 

알고리즘 분류

• 다이나믹 프로그래밍
• 배낭 문제

문제 풀이

 처음엔 그리디를 활용한 문제인 줄 알았다. 그래서 단위 시간당 중요도를 계산해서 그 결과값이 높은 순서로 수강 과목을 선정하려 했으나 오답인걸 알았다. 문제를 다시 살펴보니 DP를 사용해야 하는 문제라는 생각이 들었고 중요도와 공부시간이라는 2개의 입력이 있는 걸 보고 Knapsack을 사용할 수 있을지 생각해보았다.

 

 Knapscak 알고리즘에서는 'DP[i][j] : 무게 제한이 j일 때 i번째까지의 보석을 살펴보았을 때의 최대 가치'이다. 이를 활용하여 'DP [i][j] : 시간제한이 j일 때 i개의 과목을 넣어서 만든 최대 중요도'로 생각하여 문제를 풀었다. 

 

 같은 시간이 걸리지만 다른 중요도를 갖는 과목들이 존재하기 때문에 입력받은 과목들을 시간이 짧은 순, 시간이 같다면 중요도가 높은 순서로 정렬하였다. Knapscak 알고리즘을 사용할 때의 인덱스와 동일한 인덱스를 사용하고 싶어서 arr 배열에 [0,0]이라는 의미 없는 내용을 하나 추가하였다.

function main() {
  // 시간이 짧은순, 시간이 같다면 중요도가 높은 순으로 정렬해야한다.
  let arr = input.slice(1).map(_ => _.split(' ').map(Number));
  arr.unshift([0, 0]);
  arr.sort((a, b) => {
    let A = a[1];
    let B = b[1];
    if (A > B) return 1;
    else if (A < B) return -1;
    else {
      let A = a[0];
      let B = b[0];
      if (A > B) return -1;
      else if (A < B) return 1;
      return 0;
    }
  })

  sol(arr);
}

 

 이제 2차원 배열인 DP를 만들고 냅색 알고리즘에 따라서 문제를 풀어주면 된다. 

i번째 과목을 넣을 수 있는지?(시간 제한인 j에 걸리지 않는지)를 확인한다.

시간제한에 걸리지 않는다면 i번째 과목을 넣을 것인지, 넣지 않을것인지를 판단하여 DP를 채워준다.

function sol(arr) {
  // knapsack
  // 2차원 배열을 사용한다.
  // dp[i][j] : 시간제한이 j일때 i개의 과목을 넣어서 만든 최대 중요도

  let dp = new Array(10001).fill(null).map(_ => new Array(10001).fill(0));
  let cnt = 0;
  for (let i = 1; i <= K; i++) { // 과목.
    for (let j = 0; j <= N; j++) { // 시간.
      if(arr[i][1] > j) { // 해당 과목이 시간제한을 넘어가는 경우.
        dp[i][j] = dp[i-1][j];
      } else { // 해당 과목을 넣을것인가? 해당 과목을 넣지 않을것인가?
        dp[i][j] = Math.max(arr[i][0] + dp[i-1][j - arr[i][1]], dp[i-1][j]);
      }
    }
  }

  return console.log(dp[K][N]);
}

 

전체코드

const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
const [N, K] = input[0].split(' ').map(Number);

function sol(arr) {
  // knapsack
  // 2차원 배열을 사용한다.
  // dp[i][j] : 시간제한이 j일때 i개의 과목을 넣어서 만든 최대 중요도

  let dp = new Array(10001).fill(null).map(_ => new Array(10001).fill(0));
  let cnt = 0;
  for (let i = 1; i <= K; i++) { // 과목.
    for (let j = 0; j <= N; j++) { // 시간.
      if(arr[i][1] > j) { // 해당 과목이 시간제한을 넘어가는 경우.
        dp[i][j] = dp[i-1][j];
      } else { // 해당 과목을 넣을것인가? 해당 과목을 넣지 않을것인가?
        dp[i][j] = Math.max(arr[i][0] + dp[i-1][j - arr[i][1]], dp[i-1][j]);
      }
    }
  }

  return console.log(dp[K][N]);
}
function main() {
  // 시간이 짧은순, 시간이 같다면 중요도가 높은 순으로 정렬해야한다.
  let arr = input.slice(1).map(_ => _.split(' ').map(Number));
  arr.unshift([0, 0]);
  arr.sort((a, b) => {
    let A = a[1];
    let B = b[1];
    if (A > B) return 1;
    else if (A < B) return -1;
    else {
      let A = a[0];
      let B = b[0];
      if (A > B) return -1;
      else if (A < B) return 1;
      return 0;
    }
  })

  sol(arr);
}
main();

 

특이사항