[JAVA] 알고리즘 : 동적 계획법- 최대 점수 구하기(냅색 알고리즘)

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt(); // 문제의 개수
        int m = kb.nextInt(); // 주어진 시간
        int[] dp = new int[m+1];  // dp[i] = i분 동안 풀 수 있는 최대 점수
        for(int i=0; i<n; i++){
            int score=kb.nextInt(); // 점수
            int time=kb.nextInt(); // 시간
            for(int j=m; j>=time; j--){
                dp[j] = Math.max(dp[j], dp[j-time]+score); // 최대 점수 갱신
            }
        }
        System.out.println(dp[m]); // m분 동안의 최대 점수
    }
}

 

 

이 전 동전 교환 문제와 비슷하지만 썼던 동전을 또 쓸 수 있는 동전교환 문제와 달리

이 문제는 같은 문제를 또 풀 수 없다. 그렇기에 이중 for문을 돌 때 j가 뒤에서 거꾸로 돌며 입력받은 시간만큼을 빼준 dp[j-time]과 비교한다.