[백준] 29704 벼락치기

 

 

 

문제 출저

https://www.acmicpc.net/problem/29704

 

 

 

문제 풀이

배낭 문제로 풀었습니다. 벌금을 최소화하기 위해서는 벌금이 높은 문제들을 풀어야 합니다. 다음과 같은 점화식이 나옵니다.

    for (int i = t; i >= 0; i--) {
                if (i < d) break;
                dp[i] = Math.max(dp[i], dp[i-d] +m);
            }

 

 

 

소스코드

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

/*
벼락치기
https://www.acmicpc.net/problem/29704
 */

public class Main {

    static int n;
    static int t;
    static int[] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());
        dp = new int[t+1];

        int all = 0;
        while (n-- > 0) {
            st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            all += m;

            for (int i = t; i >= 0; i--) {
                if (i < d) break;
                dp[i] = Math.max(dp[i], dp[i-d] +m);
            }
        }

        System.out.println(all - dp[t]);


    }

}