섹션 10. dynamic programming(동적계획법) 6. 최대점수 구하기(냅색 알고리즘)

문제

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

입력

• 첫 번째 줄에 문제의 개수N(1<=N<=50)과 제한 시간 M(10<=M<=300)이 주어집니다.
• 두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.

출력

• 첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.

입출력 예제

---

풀이방식

이번 문제는 동적 계획법(dynamic programming)에 대한 문제이다.

동적 계획법 이란 시간 복잡도가 큰 문제를 직관적으로 작게 나눈다. 이렇게 나누어진 작은 문제들을 메모이제이션을 사용해서 최종적으로 본래 문제의 해결방안을 찾는 것을 말한다.

---

설계과정

1. dy 배열을 최대값으로 초기화한다.

2. dy[ ] 배열의 0번째에 0을 넣는다.

3. arr 배열에 입력받은 동전의 종류들을 coin 배열로 넘긴 후, for문을 통해 dy 배열에 값을 변경한다.

4. coin 배열을 통해 입력받은 동전에 따라 dy[ ] 배열의 값을 변경한다.

5. dy[M] 을 출력한다.

---

풀이과정

1.  각 변수들을 선언한다.

• ps : 문제 풀고 얻을 수 있는 점수
• pt : 문제 푸는데 걸리는 시간
• dy[ i ] : i까지의 시간이 지났을 때, 얻을 수 있는 크기의 점수를 저장한다.

2. M부터 pt까지 감소하는 for문으로 dy[ j ] 배열에 값을 넣는다.

• 냅색 알고리즘에서 문제의 개수가 고정되어있으면 감소 for문, 개수가 무한이면 증가 for문을 쓴다.

3. dy[ j ] 에는 dy[ j ] 와 dy[ j - pt ] + ps 를 비교해서 더 큰 값을 넣는다.

• j 가 20이고 10(ps), 5(pt) 가 입력되었다면 dy[ 20 - 5 ] 는 dy[15]로, 0이라는 값을 가진다. (배열의 초기값이 0이다.)
• 여기에 ps 값인 10을 더하면 10이 된다. 해당 과정은 dy[ j ] 에서 j가 20부터 5까지 동일하게 적용되기에 dy[ 5 ] 부터 dy[ 20 ] 의 값은 모두 10으로 저장된다.
• 위 과정을 반복하면서 배열의 값을 변경해나간다.

4. dy[M] 을 출력한다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.