최대 점수 구하기 : Dynamic Programming (냅색 알고리즘)

동전 교환 문제와 유사하게 풀 수 있다.
하지만 결정적인 차이는 '중복'해서 사용할 수 있느냐 인데,
이를 고려하지 않고 풀어서 잘못된 풀이가 나왔다!

내 풀이 - 잘못된 풀이

function solution(m, arr) {
  let answer;
  let dy = Array.from({ length: m + 1 }, () => 0); // 한 문제당 점수가 0점 이상이라는 가정

  for (let i = 0; i < arr.length; i++) {
    for (let j = arr[i][1]; j <= m; j++) {
      dy[j] = Math.max(dy[j], dy[j - arr[i][1]] + arr[i][0]);
    }
  }
  answer = dy[m];
  return answer;
}

let arr = [
  // [점수, 시간]
  [10, 5],
  [25, 12],
  [15, 8],
  [6, 3],
  [7, 4]
];
console.log(solution(20, arr));

나름 한참 고민해서 푼 풀이인데...ㅋㅋ (심지어 답도 맞게 나옴)
중복을 고려하지 않은 틀린 풀이이다.

Solution 풀이

function solution(m, arr) {
  let answer;
  let dy = Array.from({ length: m + 1 }, () => 0); // 한 문제당 점수가 0점 이상이라는 가정

  for (let i = 0; i < arr.length; i++) {
    for (let j = m; j >= arr[i][1]; j--) {
      dy[j] = Math.max(dy[j], dy[j - arr[i][1]] + arr[i][0]);
    }
  }
  answer = dy[m];
  return answer;
}

let arr = [
  // [점수, 시간]
  [10, 5],
  [25, 12],
  [15, 8],
  [6, 3],
  [7, 4]
];
console.log(solution(20, arr));

아무리 고민을 했어도 거꾸로 for문을 돌리는 아이디어 는 생각을 못했을 것 같다.
풀이를 보고도 이해가 안되서 종이에 한참 그려보면서 이해를 했다.
동전 교환 문제와 함께 중복의 유무에 따른 풀이 차이를 이해하면서 여러 번 풀어보아야 겠다.