Java : 최대 점수 구하기 (냅색)

문제

풀이

• 이전 동전 교환 문제과 마찬가지로 냅색 알고리즘을 사용해서 풀어본다.
• 이 문제는 문제 당 점수를 매기는 방식으로 개수가 제한된 문제에서 최대 점수를 뽑아내야한다.
• 동전은 동전의 개수를 무제한으로 설정되어서 계속 동전을 추가해주며 동전의 개수를 구할 수 있었는데 문제는 한 번 풀면 다시 푸는게 안 되므로 이를 생각하면서 풀어야 한다.
• j를 뒤쪽에서 시작하면 중복되지 않고 사용할 수 있다.

잡담

• 인프런 마지막 문제

전체 코드

package inflearn;

import java.util.Scanner;

public class I1006 {
	static int n, m, ans = 0;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();

		int[] dy = new int[m + 1];
		for (int i = 0; i < n; i++) {
			int score = sc.nextInt();
			int time = sc.nextInt();

			for (int j = m; j >= time; j--) {
				dy[j] = Math.max(dy[j], dy[j - time] + score);
				ans = Math.max(ans, dy[j]);
			}
		}

		System.out.println(ans);
	}
}