문제 12865

풀이 접근

1. 문제를 읽었을 때 최단경로 dp문제로 판단했다.
2. 먼저 무개와 가치에 관련된 배열 w와 v를 생성하고, dp 배열을 초기화한다.
3. dp배열을 구하기 위한 for문에서 기본적으로 i,j 인덱스의 값은 기본적으로 이전 아이템의 가치를 저장한다.
4. 만약 무게에서 자신의 무게를 뺐을 떄 남는 무게가 존재한다면 이전 아이템에서 구한 가치와 남은 무게의 가치 + 자신의 가치 중 큰 값을 가진다.
5. 원하는 dp[n][k] 값을 출력한다.

소스코드

import java.util.*;
public class boj12865 {
    static int n,k;
    static int dp[][],w[],v[];
    public static void main(String[] args)   {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        dp = new int[n+1][k+1];
        w =new int[n+1];
        v = new int[n+1];
        for(int i=1;i<=n;i++) {
            w[i] = sc.nextInt();
            v[i]= sc.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = dp[i-1][j];
                if(j-w[i] >=0){
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]] +v[i]);
                }
            }
        }
        System.out.println(dp[n][k]);
    }
}

문제핵심

• 최단경로
• DP