[백준, Java] 14728번, 벼락치기(DP)

문제 링크

14728번: 벼락치기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 시험 문제는 여러 단원이 융합되지 않으며, 각 단원별 1문제 낼 것입니다.

2. 문제를 해결하려면 해당 단원에 모든 내용을 알고 있어야 합니다.

3. 각 단원별 모든 내용을 공부하는 시간과 해당 단원에 문제를 맞추면 얻을 수 있는 점수가 주어진다.

4. 남은 시간(T)동안 공부하였을 때 최대 시험 점수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. DP[][]에 대한 탐색을 통해 최대 점수들을 저장합니다.

 

3. 탐색에서 얻은 최대 시간일 때 최대 점수를 결과로 출력합니다.

 

DP(배낭 알고리즘, 최대 점수 구하기)

 

 

1 ~ T 범위 내에서 공부를 진행했을 때 최대 점수의 값을 DP[N][T]의 저장하여 메모이제이션을 진행합니다.

 

DP[1][2] : 2초 동안 1번째 단원만 공부하였을 때 얻을 수 있는 최대 값

 

DP[2][5] : 5초 동안 1 ~ 2번째 단원까지 공부하였을 때 얻을 수 있는 최대 값

 

....

 

DP[N][T] : T초 동안 1 ~ N번째 단원까지 공부하였을 때 얻을 수 있는 최대 값

 

 

그러면, DP[][]의 값들을 어떻게 구하는 것이 이 문제에 핵심입니다.

 

각 단원에 대해서 고려하는 경우는 2가지입니다.

 

1. 해당 단원을 공부한다.

 

2. 해당 단원을 공부하지 않는다.

 

DP[i][j]로 표현하면

 

1. j초 동안 i번째 단원을 공부한다.

 

▶ 얻을 수 있는 최대 점수 : i번째 단원 문제 점수 + DP[i - 1][j - i번째 단원 공부 시간]이 될 것입니다.

 

Why??

 

DP[][]의 존재하는 값들은 최대 점수이기 때문에 DP[i-1][j - i번째 단원 공부 시간]의 값도 최대 점수로 i번째 단원을 공부하였을 때 최대값이 되기 때문입니다.

 

DP[i-1][j]의 값이 i번째 단원을 공부한 값보다 크다면, 현재 단원을 공부하지 않는 것이 최대 점수를 얻을 수 있는 방법임으로 비교를 진행해야 합니다.

 

DP[i][j] : Math.max(DP[i-1][j - i번째 단원 공부 시간] + i번째 단원 문제 점수, DP[i-1][j])으로 표현할 수 있습니다.

 

★ 단원을 공부하려고 해도 현재[ j < i번째 단원 공부 시간]을 만족한다면, 모든 내용을 학습할 수 없기 때문에 해당 단원을 학습할 수 없습니다.

 

 

2. i번째 단원을 공부하지 않는다.

 

▶ 얻을 수 있는 최대 점수 : DP[i-1][j]

 

Why??

 

i번째 단원을 공부하지 않았다면 i-1번째 단원까지 공부하였을 때 최대 점수가 그대로 최대값이 되기 때문입니다.

 

2가지 경우를 분석해서 DP[][]의 값을 구한 뒤 DP[N][K]의 값을 결과로 출력하면 최대 점수를 얻을 수 있습니다.

 

※예제 입력 과정을 살펴보시면 이해하시기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 3

 

T : 310

 

각 단원 정보

 

	시간	점수
1	50	40
2	100	70
3	200	150

 

2. DP[][]에 대한 탐색을 통해 최대 점수들을 저장합니다.

 

DP[][]을 표현하면

 

	0	1	2	3	4	...	309	310
0	0	0	0	0	0	...	0	0
1	0	0	0	0	0	...	0	0
2	0	0	0	0	0	...	0	0
3	0	0	0	0	0	...	0	0

 

 

1번째 단원 : (50, 40)

 

DP[1][1~310]까지의 최대 점수를 구하면

 

 

	0	1	...	49	50	51	...	310
0	0	0	...	0	0	0	...	0
1	0	0	...	0	40	40	...	40
2	0	0	...	0	0	0	...	0
3	0	0	...	0	0	0	...	0

 

DP[1][50]일 때부터 1번째 단원의 내용을 모두 학습할 수 있습니다.

 

DP[1][50] : Math.max(DP[0][50], DP[1][0] + 1번째 단원 문제 점수(40))

 

= DP[1][50] : Math.max(0, 40)

 

= DP[1][50] : 40

 

 

 

위 처럼 DP[][]의 값들을 다른 단원까지 모두 탐색한 결과는

 

 

	0	1	...	49	50	51	...	310
0	0	0	...	0	0	0	...	0
1	0	0	...	0	40	40	...	40
2	0	0	...	0	40	40	...	110
3	0	0	...	0	40	40	...	220

 

탐색 종료.

 

3. 탐색에서 얻은 최대 시간일 때 최대 점수를 결과로 출력합니다.

 

 

T시간 동안 얻을 수 있는 최대 점수는 DP[N][K]의 값입니다.

 

DP[3][310] : 220이 최대 점수가 됩니다.

 

220을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여  단원의 정보를 띄어쓰기 기준 나누었습니다.
• DP[][]에 메모이제이션과 식을 통해서 최대 점수들을 탐색합니다.
• 탐색이 끝났을 때 최대 점수 DP[N][T]의 값을 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

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


public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        int N = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());
        int[][] input = new int[N+1][2];
        //메모이제이션을 진행할 DP[][]
        int[][] dp = new int[N+1][T+1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine()," ");
            input[i][0] = Integer.parseInt(st.nextToken());
            input[i][1] = Integer.parseInt(st.nextToken());
        }
        //DP[][] 최대 점수 식을 통한 정보 저장
        for(int i=1;i<=N;i++){
            for(int j=1;j<=T;j++){
                //i번째 단원의 모든 내용을 학습할 수 있을 때
                if(j>= input[i][0]){
                    //1, 2번의 경우에서 최대 값을 저장합니다.
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-input[i][0]] + input[i][1]);
                }else{	//i번째 단원의 모든 내용을 학습할 수 없을 때
                    //2번의 경우만 진행하기 때문에 그대로 값을 저장합니다.
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        //탐색을 통해 얻은 최대값 DP[N][T]의 값을 BufferedWriter 저장
        bw.write(String.valueOf(dp[N][T]));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}