1. 최대점수 구하기

총시간이 주어지고 점수가 주어지고 문제를 푸는데 걸리는 시간이 주어졌을때 가장 많이 점수를 얻으려면 어떤 문제를 풀어야 하는가?

예를 들어, 아래와 같이 정보가 주어졌다고 하자

let time = 20;
let examPaper = [
  // 점수, 시간
  [10, 5],
  [25, 12],
  [15, 8],
  [6, 3],
  [7, 4],
];

// 41점

이때 1번, 2번, 4번 문제를 시간내에 풀 수 있고 이때 최대점수 41점을 얻을 수 있다.

그럼 접근 방법을 알아보자

2. 접근 방법

이전 동전문제와는 다르게 하나의 문제를 여러번 풀어서 점수를 최대화 할 수 는 없다. 그리고 20분이 한계이므로 20부터 시작해서 0으로 가는 내림차순으로 루프를 돌아야 할 것이다.

더하는 방법은 비슷하다. 다이나믹 배열에서 문제를 푸는데 걸리는 시간만큼 인덱스를 빼고 그 위치에 나온값에다가 현재 문제지의 점수를 더해서 할당하면 된다.

이것도 역시 그림으로 나타내 보았다.

결국 20분이 될 때 까지 풀 수 있는 문제들이 누적되고 그 누적된 값 들 중에 최대값이 최대점수가 되는 것이다.

function maxScore(examPaper, time) {
  let dy = Array.from({ length: time + 1 }, () => 0);

  for (let i = 0; i < examPaper.length; i++) {
    for (let j = time; j >= examPaper[i][1]; j--) {
      dy[j] = Math.min(dy[j], dy[j - examPaper[i][1]] + examPaper[i][0]);
    }
  }

  return dy;
}

다이나믹은 진짜 아무리 봐도 신박한 알고리즘이다. 잘 기억해뒀다가 잘 사용해야겠다. 이로써 인프런 알고리즘 문제 끝!