[백준] 14728 벼락치기 - Java

 

 

 

문제 출저

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

14728번: 벼락치기

 

 

 

 

문제 풀이

단원의 수(n)와 공부할 수 있는 시간(t)이 주어진다. 단원은 소요된 시간(k)과 얻을 수 있는 점수(s)로 구성되어 있다. 공부할 수 있는 시간 동안 최대 점수를 구하는게 문제이다. 

 

냅색, 배낭 알고리즘으로 풀었습니다.

1차원 int 배열을 활용했습니다. 한 단원씩 탐색을 진행합니다. 현재의 점수와 단원의 시간을 뺀 점수 + 현재 단원의 점수를 비교하여 큰 값으로 업데이트 합니다. 점화식을 세우면 다음과 같습니다. 

        int[] dp = new int[t+1];
        for (int i = 1; i <= n; i++) {
            int k = board[i][0];
            int s = board[i][1];

            // 작은 것에 큰 것으로 하면 중복이 발생한다. 이를 방지하기 위해 뒤에서부터 한다
            for (int j = t; j >= k; j--) {
                dp[j] = Math.max(dp[j], dp[j-k] + s);
            }
        }

 

k부터 t까지 탐색을 진행합니다. 이 때, t부터 k까지 역순으로 진행하는데 이유는 k부터 t까지 하면 중복이 발생하여 여러 번 더할 수 있습니다. 이를 방지하기 위해 역순으로 진행합니다.

dp[t]를 출력해 정답을 나타냅니다. 

 

 

 

 

소스 코드

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


/*
벼락치지
https://www.acmicpc.net/problem/14728

2차원 배열로 k ~ t 까지 하면 k 이전의 값이 없어서 오답이 된다.
 */

public class Main {

    static int n; // 단원 개수
    static int t; // 시간
    static int[][] board;

    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());
        board = new int[n+1][2];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            board[i][0] = k;
            board[i][1] = s;
        }

        int[] dp = new int[t+1];
        for (int i = 1; i <= n; i++) {
            int k = board[i][0];
            int s = board[i][1];

            // 작은 것에 큰 것으로 하면 중복이 발생한다. 이를 방지하기 위해 뒤에서부터 한다
            for (int j = t; j >= k; j--) {
                dp[j] = Math.max(dp[j], dp[j-k] + s);
            }
        }



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

    }

}