[백준/14728] 벼락치기 - JAVA

📌 문제

알고리즘 분류 : DP
난이도 : 골드5
출처 : 백준 - 벼락치기

🦧 문제 풀이 접근

간단한 DP알고리즘 배낭문제 유형이다.
2차원 DP배열을 만들어서 배점이 1인 경우부터 차근차근 dp배열을 채워가면 된다.

💻 code

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());
        int dp[][] = new int[N+1][T+1];
        for(int i=1;i<=N;i++) {
            st = new StringTokenizer(br.readLine());
            int K = Integer.parseInt(st.nextToken());//공부 시간
            int 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],dp[i-1][j-K]+S);
            }
        }
        System.out.println(dp[N][T]);
    }
}

🥇 결과

🎓 느낀점

배낭문제 유형 기초 문제다. 전혀 어렵지 않다.