[자바] 백준 14728 - 벼락치기 (java)

목차

• 문제 : boj14728
• 필요 알고리즘
• 풀이
• 코드 : github

문제 : boj14728

 

 

필요 알고리즘

• DP, 냅색 (배낭 문제)
  
  • DP로 해결 가능한 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  dp[x]를 x시간을 사용해 얻을 수 있는 최대 점수라고 해보자.

그렇다면 현재 단원에 대한 K와 S가 주어졌을 때, x시간을 사용해 얻을 수 있는 최대 점수는, '현재까지 파악한 x시간을 사용해 얻을 수 있는 최대 점수', 'x-K 시간까지 얻을 수 있는 최대 점수에 이번 단원을 공부하여 얻은 S점을 더한 것' 중에 큰 걸 택하면 된다.

 

  위의 말을 점화식으로 나타내면 dp[x] = max(dp[x], dp[x-K]+S) 이다. 그럼 이걸 그냥 구현하기만 하면 된다. 코드 자체도 그냥 입력받고, 위 수식을 적용하기만 한 것이다. 여기서 for (int i = t; i >= k; i--) 처럼 dp[t]부터 점차 이전시간으로 진행하며 점화식을 적용한 이유는, 그렇게 하지 않으면 현재 보고 있는 단원이 여러번 연산 상에 적용될 수 있기 때문이다.

 

  무슨말이냐면 입력이 아래와 같다고 해보자.

1 100
1 10

 

  당연하게도 0~100 시간 이내에 1의 시간만 사용 가능하며, 답은 '10'이다.

근데 시간이 작은 부분부터 저 수식을 적용하면 답이 '1000'이 나오게 될 것이다. 이걸 처리하기 위해 다른 방식을 적용해도 되지만, 귀찮을 것이므로 그냥 뒤에서 부터 보면 해결된다.

 

 

코드 : github

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

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

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());

        int[] dp = new int[t+1];
        while (n-->0) {
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());

            for (int i = t; i >= k; i--) {
                dp[i] = Math.max(dp[i], dp[i-k] + s);
            }
        }

        System.out.println(dp[t]);
    }
}