문제 링크
주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}
문제 설명
접근 방법
이 문제에 핵심
1. 시험 문제는 여러 단원이 융합되지 않으며, 각 단원별 1문제 낼 것입니다.
2. 문제를 해결하려면 해당 단원에 모든 내용을 알고 있어야 합니다.
3. 각 단원별 모든 내용을 공부하는 시간과 해당 단원에 문제를 맞추면 얻을 수 있는 점수가 주어진다.
4. 남은 시간(T)동안 공부하였을 때 최대 시험 점수를 결과로 출력합니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. DP[][]에 대한 탐색을 통해 최대 점수들을 저장합니다.
3. 탐색에서 얻은 최대 시간일 때 최대 점수를 결과로 출력합니다.
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 |
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 |
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. 탐색에서 얻은 최대 시간일 때 최대 점수를 결과로 출력합니다.
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();
}
}
'백준' 카테고리의 다른 글
[백준, Java] 25606번, 장마, (누적합) (2) | 2024.01.22 |
---|---|
[백준, Java] 12101번, 1, 2, 3 더하기 2, (백트레킹) (2) | 2024.01.21 |
[백준, Java] 17611번, 직각다각형(누적합) (6) | 2024.01.09 |
[백준, Java] 27210번, 신을 모시는 사당(누적합, DP) (4) | 2024.01.03 |
[백준, Java] 17129번, 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유(BFS) (2) | 2023.12.27 |
댓글