문제 링크
25605번: 입맛이 까다로운 코알라가 유칼립투스 잎을 행복하게 먹을 수 있는 방법
판다는 주식으로 대나무를 먹고, 개미핥기는 주식으로 개미와 흰개미를 먹듯이 코알라는 유칼립투스 잎을 주식으로 먹고 있다.유칼립투스 잎에는 독성이 있어서 다른 초식동물들은 유칼립투스 잎을 먹지 못하지만, 코알라는 유칼립투스 잎에 있는 독성을 해독할 수 있는 유전자를 지니고 있기 때문에 먹이 경쟁 없이 살아남을 수 있게 되었다...
www.acmicpc.net
주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}문제 설명
접근 방법
이 문제에 핵심
1. 코알라는 유칼립투스 잎을 먹으면 독이 축적되지만, 행복도가 올라갑니다.
2. 코알라는 독을 축적하는 한계가 존재하여 한계에 도달하면 죽으며, 매일 B만큼 해독을 진행합니다.
3. 코알라는 M일 동안 잎을 순서대로 먹으며, 하루에 최대 1개만 먹습니다.
4. 코알라는 잎을 버릴 수 있으며, 모든 잎에 행동이 끝나면 더 이상 잎을 주지 않습니다.
5. 각 잎마다 독소와 행복도가 정해져 있습니다.
6. 사육사가 M일 동안 순서대로 잎을 줄 때 최대 행복도를 결과로 출력합니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. 점화식을 통해서 코알라가 M일까지 잎을 먹는 경우에 최대 행복도를 탐색합니다.
3. 탐색을 통해 M일이 되었을 때 코알라의 최대 행복도를 결과를 출력합니다.
행복도 탐색(DP)
각 날짜마다 코알라는 3가지 행동을 할 수 있습니다.
if(basic + leaf[j][0] <= A){
tempToxic = Math.max(basic + leaf[j][0] - B, 0);
DP[i][j][tempToxic] = leaf[j][1];
}DP[i][j][k] = Math.max(DP[i][j][k], DP[i][j-1][k]);tempToxic = Math.max(k - B, 0);
DP[i][j][tempToxic] = Math.max(DP[i][j][tempToxic], DP[i-1][j][k]);if(DP[i-1][j-1][k] != 0 && k + leaf[j][0] <= A){
tempToxic = Math.max(k + leaf[j][0] - B, 0);
DP[i][j][tempToxic] = Math.max(DP[i][j][tempToxic], DP[i-1][j-1][k] + leaf[j][1]);
}
예제입력 1.
1. 입력된 정보를 저장합니다.
N = 5
M = 10
[독소 정보]
| A | B | C |
| 50 | 0 | 0 |
[잎 정보]
| 독소 | 행복도 | |
| 잎1 | 10 | 10 |
| 잎2 | 20 | 20 |
| 잎3 | 30 | 30 |
| 잎4 | 40 | 40 |
| 잎5 | 50 | 50 |
2. 점화식을 통해서 코알라가 M일까지 잎을 먹는 경우에 최대 행복도를 탐색합니다.
DP[i][j][k] : i번째 날 1 ~ j번째 잎을 먹을 수 있으며, 현재 독소가 k인 최대 행복도
2) 코알라가 i번째 날 j번째 잎을 먹는 것보다 1 ~ (j-1)까지 잎 중 먹은 최대 행복도가 더 높을 수 있습니다.
DP[1][1][1] = Math.max(DP[1][1][1], DP[1][0][1]) : 0
...
DP[1][5][50] = Math.max(DP[1][5][50], DP[1][4][50]) : 50
3) 코알라가 잎을 먹지 않았을 때
DP[1][1][1] = Math.max(DP[1][1][1], DP[0][1 - B]) = 0
...
DP[1][5][50] = Math.max(DP[1][5][50], DP[0][5][50]) : 50
4) 코알라가 i번째날 j번의 잎을 먹었을 때
1번째 날에는 DP[i-1][j-1][k] 값이 모두 0이기 때문에 탐색하지 않습니다.
또한, 1)에서 i번째 날 k번째 잎을 처음 먹는 것이랑 똑같기 때문입니다.
3. 탐색을 통해 M일이 되었을 때 코알라의 최대 행복도를 결과를 출력합니다.
- BufferedReader를 사용하여 입력되는 정보를 저장합니다.
- StringTokenizer을 통해 코알라, 잎, 요일 정보들을 띄어쓰기 기준 나누었습니다.
- DP[1~M][1~N][K]에 대해서 점화식을 기준으로 탐색합니다.
- M일이 지났을 때 최대 행복도를 가리키는 DP[M][N][1~A]에 최대 값을 구합니다.
- 최대 행복도의 값을 결과로 BufferdWriter 저장합니다.
- BufferedWriter에 저장된 결과를 출력합니다.
결과코드
import java.io.*;
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 M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine()," ");
//코알라 정보 저장
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
int[][] leaf = new int[N+1][2];
//잎 정보 저장
//0 : 독의 양, 1 : 행복도
for(int i=1;i<=N;i++){
st = new StringTokenizer(br.readLine()," ");
leaf[i][0] = Integer.parseInt(st.nextToken());
leaf[i][1] = Integer.parseInt(st.nextToken());
}
//점화식을 통한 DP[i][j][k] 탐색
int basic = C + B;
int[][][] DP = new int[M+1][N+1][A+1];
for(int i=1;i<=M;i++){
basic = Math.max(basic - B, 0);
int tempToxic;
for(int j=1;j<=N;j++){
//1)
if(basic + leaf[j][0] <= A){
tempToxic = Math.max(basic + leaf[j][0] - B, 0);
DP[i][j][tempToxic] = leaf[j][1];
}
for(int k=0;k<=A;k++){
//2)
tempToxic = Math.max(k - B, 0);
DP[i][j][tempToxic] = Math.max(DP[i][j][tempToxic], DP[i-1][j][k]);
//3)
DP[i][j][k] = Math.max(DP[i][j][k], DP[i][j-1][k]);
//4)
if(DP[i-1][j-1][k] != 0 && k + leaf[j][0] <= A){
tempToxic = Math.max(k + leaf[j][0] - B, 0);
DP[i][j][tempToxic] = Math.max(DP[i][j][tempToxic], DP[i-1][j-1][k] + leaf[j][1]);
}
}
}
}
int result = 0;
//DP[M][N][1 ~ A]까지 중 최대 값 = 최대 행복도를 찾습니다.
for(int i=0;i<=A;i++){
result = Math.max(result, DP[M][N][i]);
}
bw.write(String.valueOf(result)); //최대 행복도를 BufferedWriter 저장
bw.flush(); //결과 출력
bw.close();
br.close();
}
}'백준' 카테고리의 다른 글
| [백준, Java] 27211번, 도넛 행성(BFS) (0) | 2024.07.30 |
|---|---|
| [백준, Java] 1036번, 36진수(그리디) (7) | 2024.07.22 |
| [백준, Java] 1562번, 계단 수, [DP, 비트마스킹] (0) | 2024.07.02 |
| [백준, Java] 1513번, 경로 찾기, [DP] (2) | 2024.06.25 |
| [백준, Java] 1519번, 부분 문자열 뽑기 게임, [DP, 그리디] (0) | 2024.06.21 |
댓글