문제링크
오늘은 배낭 알고리즘 극복을 위한 문제를 가져와봤습니다.
문제는 간단합니다. 세준이는 한 사람에게 인사를 할 때마다 체력이 고갈되고, 행복이 늘게 됩니다. 정해진 체력인 100 안에서 세준이의 최대 행복치를 찾아주면 되는 전형적인 배낭 문제입니다.
1. 기본 세팅
예제 입력1로 설명해보자면
현재 제 코드에서 각 사람에 대한 체력, 기쁨은 아래와 같이 표현됩니다.
HP[ ] : 1 21 79
JOY[ ] : 20 30 25
세준이의 체력은 100이 되면 죽는 것으로 간주하기에 최종답이 저장될 dp 배열을
dp = new int[100]
으로 설정하였습니다.
2. 해결법
해결법은 간단합니다. 한 사람마당 dp 배열을 99에서부터 해당 사람이 깎을 수 있는 체력인덱스까지 반복문을 진행하며 dp 배열에 해당 사람이랑 인사한 값과 인사하지 않은 값 중 더 큰 값을 넣어주면 됩니다.
즉, dp에 대한 식은 아래와 같이 진행될 것입니다.
for(int i=1; i<=N; i++){ //사람 수 체크
for(int j=99; j>=0; j--) {
//1. 현재 j가 봐야할 체력수보다 크거나 "같은" 경우
if(j>=hp[i]) {
dp[j] = Math.max(dp[j], dp[j-hp[i]] + joy[i]);
// 현재 인사 안 한 경우 vs 한 경우
}
}
}현재 체력 뺀 경우 vs 안 뺀 경우
이게 어떤 소리인지 예시를 들며 설명해보겠습니다.
1번 사람
hp[1] = 1
joy[1] ] 20
DP [99] = Math.max(dp[99], dp[99-hp[1]] + joy[1])
.
.
.
.
DP[0] = 0
2번 사람
hp[2] = 21
joy[2] = 30
DP[99] = Math.max(dp[99], dp[99-hp[2]] + joy[2])
= Math.max(dp[99], 20 + 30)
= 50
.
.
.
.
dp[22] = 50
dp[21] = 20
3번 사람
hp[3] = 79
joy[3] = 25
dp[99] = 50 vs (20+25) = 50
.
.
.
.
dp[80] = 50
dp[29] = 50
⭐ 주의할 점
위 코드에서 첫 번째 if문 주석에
//1. 현재 j가 봐야할 체력수보다 크거나 "같은" 경우
라는 부분이 있을 겁니다.
왜 일까요? 세준이는 분명 체력이 0이 되면 죽는다고 했는데 그럼 math.max 함수를 통해 최신화를 해주는게 아니라 그냥 dp값은 0인거 아닌가요?
라고 생각해서 제가 1차 관문을 틀렸었습니다
ㅎㅎ
문제를 다시 읽어보면
만약 세준이의 체력이 0이나 음수가 되면, 죽어서 아무런 기쁨을 못 느낀 것이 된다
즉 죽었을때의 기쁨은 0이 되는 게 아니라 hp만 깎이고 기쁨은 얻지 못한 상태가 된다는 의미입니다.
이를 조심해서 부등호는 >= 으로 지정해주니 코드가 성공적으로 통과가 될 수 있었습니다.
