[백준][Java] 14728 - 벼락치기

목차

 

문제 정보

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

14728번: 벼락치기

난이도 : Gold 5

유형 : 0/1 냅색(DP), 브루트포스

시간 : O(N * T)

 

 

(냅색문제에 잘 모른다면 이 분의 글을 읽는 것을 추천한다. 설명이 아주 기깔나고 잘하셨다.)

https://gsmesie692.tistory.com/113

Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)

출처 : https://gsmesie692.tistory.com/

---

문제 풀이

아주 스탠다드한 0/1 냅색 문제이다.

변수 2개를 이용한 2차원 dp테이블 만들어 활용하면 된다.

 

1. 단원의 갯수 - row

2. 총 시간 - column

 

점화식)

k 는 1 ~ T까지의 수 (세로열)

j < k 일 때
dp[i][j] = dp[i-1][j]

j >= k 일 때
dp[i][j] = Math.max(dp[i-1][j-k] + S, dp[i-1][j])

---

코드

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

public class Main {

    private int N, T;
    private int K, S;
    private int[][] dp;

    public void solution() 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[N + 1][T + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            K = Integer.parseInt(st.nextToken());
            S = Integer.parseInt(st.nextToken());

            for (int j = 1; j <= T; j++) {
                if (j < K) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - K] + S, dp[i - 1][j]);
                }
            }
        }

        System.out.println(dp[N][T]);
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}