문제

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩 니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)

입출력 예제

입력 : [[10, 5], [25, 12], [15,8], [6,3], [7,4]], 20
출력 : 41

코드

function solution(m, arr){  
  let answer=0;
  //	인덱스 분(minute) 동안 풀 수 있는 최댓값
  let dy=Array.from({length:m+1}, ()=>0);
  //	문제 갯수 처음부터 돌면서
  for(let i=0; i<arr.length; i++){
    let ps=arr[i][0];	// 문제 풀면 받을 수 있는 점수
    let pt=arr[i][1];	// 문제 푸는데 걸리는 시간
    //	최대 시간부터 줄여가면서
    for(let j=m; j>=pt; j--){
      //	현재 저장된 값과 현재 문제 풀기 전 최고 값이랑 더한 값 비교
      dy[j]=Math.max(dy[j], dy[j-pt]+ps);
    }
  }
  answer=dy[m];
  return answer;
}

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

나중에 다시 봤을 때 이해 되도록 콘솔도 찍어서 확인했다.

i:0, ps:10, pt:5
j:20, dy[j]:0, dy[j-pt]:0
[
  0, 0, 0, 0, 0, 0,  0,
  0, 0, 0, 0, 0, 0,  0,
  0, 0, 0, 0, 0, 0, 10
]

j:19, dy[j]:0, dy[j-pt]:0
[
  0, 0, 0, 0, 0,  0,  0,
  0, 0, 0, 0, 0,  0,  0,
  0, 0, 0, 0, 0, 10, 10
]

j:18, dy[j]:0, dy[j-pt]:0
[
  0, 0, 0, 0,  0,  0,  0,
  0, 0, 0, 0,  0,  0,  0,
  0, 0, 0, 0, 10, 10, 10
]

j:17, dy[j]:0, dy[j-pt]:0
[
  0, 0, 0,  0,  0,  0,  0,
  0, 0, 0,  0,  0,  0,  0,
  0, 0, 0, 10, 10, 10, 10
]

j:16, dy[j]:0, dy[j-pt]:0
[
  0, 0,  0,  0,  0,  0,  0,
  0, 0,  0,  0,  0,  0,  0,
  0, 0, 10, 10, 10, 10, 10
]

j:15, dy[j]:0, dy[j-pt]:0
[
  0,  0,  0,  0,  0,  0,  0,
  0,  0,  0,  0,  0,  0,  0,
  0, 10, 10, 10, 10, 10, 10
]

j:14, dy[j]:0, dy[j-pt]:0
[
   0,  0,  0,  0,  0,  0,  0,
   0,  0,  0,  0,  0,  0,  0,
  10, 10, 10, 10, 10, 10, 10
]

j:13, dy[j]:0, dy[j-pt]:0
[
   0,  0,  0,  0,  0,  0,  0,
   0,  0,  0,  0,  0,  0, 10,
  10, 10, 10, 10, 10, 10, 10
]

j:12, dy[j]:0, dy[j-pt]:0
[
   0,  0,  0,  0,  0,  0,  0,
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 10, 10
]

j:11, dy[j]:0, dy[j-pt]:0
[
   0,  0,  0,  0,  0,  0,  0,
   0,  0,  0,  0, 10, 10, 10,
  10, 10, 10, 10, 10, 10, 10
]

j:10, dy[j]:0, dy[j-pt]:0
[
   0,  0,  0,  0,  0,  0,  0,
   0,  0,  0, 10, 10, 10, 10,
  10, 10, 10, 10, 10, 10, 10
]

j:9, dy[j]:0, dy[j-pt]:0
[
   0,  0,  0,  0,  0,  0,  0,
   0,  0, 10, 10, 10, 10, 10,
  10, 10, 10, 10, 10, 10, 10
]

j:8, dy[j]:0, dy[j-pt]:0
[
   0,  0,  0,  0,  0,  0,  0,
   0, 10, 10, 10, 10, 10, 10,
  10, 10, 10, 10, 10, 10, 10
]

j:7, dy[j]:0, dy[j-pt]:0
[
   0,  0,  0,  0,  0,  0,  0,
  10, 10, 10, 10, 10, 10, 10,
  10, 10, 10, 10, 10, 10, 10
]

j:6, dy[j]:0, dy[j-pt]:0
[
   0,  0,  0,  0,  0,  0, 10,
  10, 10, 10, 10, 10, 10, 10,
  10, 10, 10, 10, 10, 10, 10
]

j:5, dy[j]:0, dy[j-pt]:0
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 10, 10,
  10, 10, 10, 10, 10, 10, 10
]

i:1, ps:25, pt:12
j:20, dy[j]:10, dy[j-pt]:10
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 10, 10,
  10, 10, 10, 10, 10, 10, 35
]

j:19, dy[j]:10, dy[j-pt]:10
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 10, 10,
  10, 10, 10, 10, 10, 35, 35
]

j:18, dy[j]:10, dy[j-pt]:10
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 10, 10,
  10, 10, 10, 10, 35, 35, 35
]

j:17, dy[j]:10, dy[j-pt]:10
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 10, 10,
  10, 10, 10, 35, 35, 35, 35
]

j:16, dy[j]:10, dy[j-pt]:0
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 10, 10,
  10, 10, 25, 35, 35, 35, 35
]

j:15, dy[j]:10, dy[j-pt]:0
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 10, 10,
  10, 25, 25, 35, 35, 35, 35
]

j:14, dy[j]:10, dy[j-pt]:0
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 10, 10,
  25, 25, 25, 35, 35, 35, 35
]

j:13, dy[j]:10, dy[j-pt]:0
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 10, 25,
  25, 25, 25, 35, 35, 35, 35
]

j:12, dy[j]:10, dy[j-pt]:0
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 25, 25,
  25, 25, 25, 35, 35, 35, 35
]

i:2, ps:15, pt:8
j:20, dy[j]:35, dy[j-pt]:25
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 25, 25,
  25, 25, 25, 35, 35, 35, 40
]

j:19, dy[j]:35, dy[j-pt]:10
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 25, 25,
  25, 25, 25, 35, 35, 35, 40
]

j:18, dy[j]:35, dy[j-pt]:10
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 25, 25,
  25, 25, 25, 35, 35, 35, 40
]

j:17, dy[j]:35, dy[j-pt]:10
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 25, 25,
  25, 25, 25, 35, 35, 35, 40
]

j:16, dy[j]:25, dy[j-pt]:10
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 25, 25,
  25, 25, 25, 35, 35, 35, 40
]

j:15, dy[j]:25, dy[j-pt]:10
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 25, 25,
  25, 25, 25, 35, 35, 35, 40
]

j:14, dy[j]:25, dy[j-pt]:10
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 25, 25,
  25, 25, 25, 35, 35, 35, 40
]

j:13, dy[j]:25, dy[j-pt]:10
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 25, 25,
  25, 25, 25, 35, 35, 35, 40
]

j:12, dy[j]:25, dy[j-pt]:0
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 10, 25, 25,
  25, 25, 25, 35, 35, 35, 40
]

j:11, dy[j]:10, dy[j-pt]:0
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 10, 15, 25, 25,
  25, 25, 25, 35, 35, 35, 40
]

j:10, dy[j]:10, dy[j-pt]:0
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 10, 15, 15, 25, 25,
  25, 25, 25, 35, 35, 35, 40
]

j:9, dy[j]:10, dy[j-pt]:0
[
   0,  0,  0,  0,  0, 10, 10,
  10, 10, 15, 15, 15, 25, 25,
  25, 25, 25, 35, 35, 35, 40
]

j:8, dy[j]:10, dy[j-pt]:0
[
   0,  0,  0,  0,  0, 10, 10,
  10, 15, 15, 15, 15, 25, 25,
  25, 25, 25, 35, 35, 35, 40
]

i:3, ps:6, pt:3
j:20, dy[j]:40, dy[j-pt]:35
[
   0,  0,  0,  0,  0, 10, 10,
  10, 15, 15, 15, 15, 25, 25,
  25, 25, 25, 35, 35, 35, 41
]

j:19, dy[j]:35, dy[j-pt]:25
[
   0,  0,  0,  0,  0, 10, 10,
  10, 15, 15, 15, 15, 25, 25,
  25, 25, 25, 35, 35, 35, 41
]

j:18, dy[j]:35, dy[j-pt]:25
[
   0,  0,  0,  0,  0, 10, 10,
  10, 15, 15, 15, 15, 25, 25,
  25, 25, 25, 35, 35, 35, 41
]

j:17, dy[j]:35, dy[j-pt]:25
[
   0,  0,  0,  0,  0, 10, 10,
  10, 15, 15, 15, 15, 25, 25,
  25, 25, 25, 35, 35, 35, 41
]

j:16, dy[j]:25, dy[j-pt]:25
[
   0,  0,  0,  0,  0, 10, 10,
  10, 15, 15, 15, 15, 25, 25,
  25, 25, 31, 35, 35, 35, 41
]

j:15, dy[j]:25, dy[j-pt]:25
[
   0,  0,  0,  0,  0, 10, 10,
  10, 15, 15, 15, 15, 25, 25,
  25, 31, 31, 35, 35, 35, 41
]

j:14, dy[j]:25, dy[j-pt]:15
[
   0,  0,  0,  0,  0, 10, 10,
  10, 15, 15, 15, 15, 25, 25,
  25, 31, 31, 35, 35, 35, 41
]

j:13, dy[j]:25, dy[j-pt]:15
[
   0,  0,  0,  0,  0, 10, 10,
  10, 15, 15, 15, 15, 25, 25,
  25, 31, 31, 35, 35, 35, 41
]

j:12, dy[j]:25, dy[j-pt]:15
[
   0,  0,  0,  0,  0, 10, 10,
  10, 15, 15, 15, 15, 25, 25,
  25, 31, 31, 35, 35, 35, 41
]

j:11, dy[j]:15, dy[j-pt]:15
[
   0,  0,  0,  0,  0, 10, 10,
  10, 15, 15, 15, 21, 25, 25,
  25, 31, 31, 35, 35, 35, 41
]

j:10, dy[j]:15, dy[j-pt]:10
[
   0,  0,  0,  0,  0, 10, 10,
  10, 15, 15, 16, 21, 25, 25,
  25, 31, 31, 35, 35, 35, 41
]

j:9, dy[j]:15, dy[j-pt]:10
[
   0,  0,  0,  0,  0, 10, 10,
  10, 15, 16, 16, 21, 25, 25,
  25, 31, 31, 35, 35, 35, 41
]

j:8, dy[j]:15, dy[j-pt]:10
[
   0,  0,  0,  0,  0, 10, 10,
  10, 16, 16, 16, 21, 25, 25,
  25, 31, 31, 35, 35, 35, 41
]

j:7, dy[j]:10, dy[j-pt]:0
[
   0,  0,  0,  0,  0, 10, 10,
  10, 16, 16, 16, 21, 25, 25,
  25, 31, 31, 35, 35, 35, 41
]

j:6, dy[j]:10, dy[j-pt]:0
[
   0,  0,  0,  0,  0, 10, 10,
  10, 16, 16, 16, 21, 25, 25,
  25, 31, 31, 35, 35, 35, 41
]

j:5, dy[j]:10, dy[j-pt]:0
[
   0,  0,  0,  0,  0, 10, 10,
  10, 16, 16, 16, 21, 25, 25,
  25, 31, 31, 35, 35, 35, 41
]

j:4, dy[j]:0, dy[j-pt]:0
[
   0,  0,  0,  0,  6, 10, 10,
  10, 16, 16, 16, 21, 25, 25,
  25, 31, 31, 35, 35, 35, 41
]

j:3, dy[j]:0, dy[j-pt]:0
[
   0,  0,  0,  6,  6, 10, 10,
  10, 16, 16, 16, 21, 25, 25,
  25, 31, 31, 35, 35, 35, 41
]

i:4, ps:7, pt:4
j:20, dy[j]:41, dy[j-pt]:31
[
   0,  0,  0,  6,  6, 10, 10,
  10, 16, 16, 16, 21, 25, 25,
  25, 31, 31, 35, 35, 35, 41
]

j:19, dy[j]:35, dy[j-pt]:31
[
   0,  0,  0,  6,  6, 10, 10,
  10, 16, 16, 16, 21, 25, 25,
  25, 31, 31, 35, 35, 38, 41
]

j:18, dy[j]:35, dy[j-pt]:25
[
   0,  0,  0,  6,  6, 10, 10,
  10, 16, 16, 16, 21, 25, 25,
  25, 31, 31, 35, 35, 38, 41
]

j:17, dy[j]:35, dy[j-pt]:25
[
   0,  0,  0,  6,  6, 10, 10,
  10, 16, 16, 16, 21, 25, 25,
  25, 31, 31, 35, 35, 38, 41
]

j:16, dy[j]:31, dy[j-pt]:25
[
   0,  0,  0,  6,  6, 10, 10,
  10, 16, 16, 16, 21, 25, 25,
  25, 31, 32, 35, 35, 38, 41
]

j:15, dy[j]:31, dy[j-pt]:21
[
   0,  0,  0,  6,  6, 10, 10,
  10, 16, 16, 16, 21, 25, 25,
  25, 31, 32, 35, 35, 38, 41
]

j:14, dy[j]:25, dy[j-pt]:16
[
   0,  0,  0,  6,  6, 10, 10,
  10, 16, 16, 16, 21, 25, 25,
  25, 31, 32, 35, 35, 38, 41
]

j:13, dy[j]:25, dy[j-pt]:16
[
   0,  0,  0,  6,  6, 10, 10,
  10, 16, 16, 16, 21, 25, 25,
  25, 31, 32, 35, 35, 38, 41
]

j:12, dy[j]:25, dy[j-pt]:16
[
   0,  0,  0,  6,  6, 10, 10,
  10, 16, 16, 16, 21, 25, 25,
  25, 31, 32, 35, 35, 38, 41
]

j:11, dy[j]:21, dy[j-pt]:10
[
   0,  0,  0,  6,  6, 10, 10,
  10, 16, 16, 16, 21, 25, 25,
  25, 31, 32, 35, 35, 38, 41
]

j:10, dy[j]:16, dy[j-pt]:10
[
   0,  0,  0,  6,  6, 10, 10,
  10, 16, 16, 17, 21, 25, 25,
  25, 31, 32, 35, 35, 38, 41
]

j:9, dy[j]:16, dy[j-pt]:10
[
   0,  0,  0,  6,  6, 10, 10,
  10, 16, 17, 17, 21, 25, 25,
  25, 31, 32, 35, 35, 38, 41
]

j:8, dy[j]:16, dy[j-pt]:6
[
   0,  0,  0,  6,  6, 10, 10,
  10, 16, 17, 17, 21, 25, 25,
  25, 31, 32, 35, 35, 38, 41
]

j:7, dy[j]:10, dy[j-pt]:6
[
   0,  0,  0,  6,  6, 10, 10,
  13, 16, 17, 17, 21, 25, 25,
  25, 31, 32, 35, 35, 38, 41
]

j:6, dy[j]:10, dy[j-pt]:0
[
   0,  0,  0,  6,  6, 10, 10,
  13, 16, 17, 17, 21, 25, 25,
  25, 31, 32, 35, 35, 38, 41
]

j:5, dy[j]:10, dy[j-pt]:0
[
   0,  0,  0,  6,  6, 10, 10,
  13, 16, 17, 17, 21, 25, 25,
  25, 31, 32, 35, 35, 38, 41
]

j:4, dy[j]:6, dy[j-pt]:0
[
   0,  0,  0,  6,  7, 10, 10,
  13, 16, 17, 17, 21, 25, 25,
  25, 31, 32, 35, 35, 38, 41
]

41