[백준] 14728 벼락치기

www.acmicpc.net/problem/14728

14728번: 벼락치기

2021-01-07

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main14728 {
    public static int N, T, time[], points[] , dp[][];
    
    public static void solve() {
        for(int i = 1; i <= N; i++) {
            for(int p = 0; p <= T; p++) {
                if(p - time[i] < 0) dp[i][p] = dp[i-1][p];
                else dp[i][p] = Math.max(dp[i-1][p], dp[i-1][p-time[i]] + points[i]);
            }
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());
        
        time = new int[N+1];
        points = new int[N+1];
        dp = new int[N+1][T+1];
        
        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(bf.readLine());
            time[i] = Integer.parseInt(st.nextToken());
            points[i] = Integer.parseInt(st.nextToken());
        }
        solve();
        System.out.println(dp[N][T]);
    }
}
 

 

#문제풀이

0/1 knapsack 문제로, 복습 차원에서 풀어봤다.

아래 문제와 같은 방법으로 풀면된다.

 

void2017.tistory.com/165

[백준] 12865 평범한 배낭

 

다른 점은 '평범한 배낭' 문제는 값을 2차원 배열로 저장했었는데, 이번에는 time과 points 각각 다른 1차원 배열로 저장했다.