최대점수 구하기(DP-냅색 알고리즘)

해당 문제는 인프런의 강의를 들으며 정리한 Dynamic Programming 문제이다.

문제 풀이 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	/**
	 * 시간내 최대점수 구할시 배열 스코어 끝에서부터 탐색해야 함!!!
	 * 
	 * @param args
	 * @throws IOException
	 */
	public static void main(String[] args) throws IOException {
		// 최대점수 구하기(냅색 알고리즘)
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken()); // 문제의 개수
		int M = Integer.parseInt(st.nextToken()); // 제한 시간

		int[] maxScore = new int[M + 1];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int score = Integer.parseInt(st.nextToken());
			int time = Integer.parseInt(st.nextToken());

			// !! 중요사항 - 배열 끝부터 탐색 !!
			for (int j = M; j >= time; j--) {
				// 현재 MAX 스코어보다 이전 시간의 스코어가 높다면
				maxScore[j] = Math.max(maxScore[j], maxScore[j - time] + score);
			}
		}
		System.out.println(maxScore[M]);
	}
}

정리

1. 동적 프로그래밍 문제는 기본적으로 최댓값,최솟값등을 구하기 위하여 배열을 재사용한다는 것을 인지한다.

2. 문제의 핵심 중 하나는 시간내에 가장 높은 점수를 구하기 위해 앞에서 탐색하는 Bottom-UP 방식이 아닌 배열 끝에서부터 탐색하는 Top-Down 방식을 사용해야 한다.

3. 현재 시간별 최대스코어 배열(maxScore)에 값이 존재하는 경우  (현재 최대스코어 < (현재시간-감소시간)의 최대스코어 + (감소시간의 점수) ) 일경우 더 높은 값으로 대체한다.

4. 결론적으로 배열 끝부터 시간마다 모든 점수를 입력하여 그 시점에 더한 값이 더 높은 값이 있다면 변경해준다.

 

결론

동적 프로그래밍은 매번 느끼지만, 익숙해지는데에 어려움이 있다. 오늘 강의를 통해 평소에 이해가 되지 않던 내용이 조금이나마 이해가 되었다. 이 글을 읽는 개발자분들도 그림이나 표를 참조하여 설명을 듣는다면 이해하기 수월해질것이라고 생각한다. 더 열심히 들어보자...