문제
세준이는 체력 100으로 시작한다. N명에게 인사하면 체력이 감소하고 기쁨을 얻는다. 체력이 0 이하가 되면 죽으므로, 체력을 1 이상 유지하면서 얻을 수 있는 최대 기쁨을 구하라.
입력
첫째 줄에 N (1 이상 20 이하), 둘째 줄에 체력 소모 값, 셋째 줄에 기쁨 값이 주어진다.
출력
최대 기쁨을 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 1 21 79 20 30 25 | 50 |
풀이
0/1 배낭 문제로 풀이한다. 용량은 체력 99 (100-1), 무게는 체력 소모, 가치는 기쁨이다.
dp[i][j]를 i번째 사람까지 고려하고 체력 j가 남았을 때의 최대 기쁨으로 정의한다L[i] <= j이면 인사하는 경우와 안 하는 경우 중 최대를 선택한다dp[i][j] = max(dp[i-1][j-L[i]] + J[i], dp[i-1][j])dp[N][99]가 답이다
핵심 아이디어: 체력이 0 이하가 되면 안 되므로, 용량을 99로 설정한 0/1 배낭 문제와 동일하다.
코드
package day399;
import java.io.*;
import java.util.*;
public class Day390BOJ1535안녕 {
static int N, max = 99;
static int[] L, J;
static int[][] dp;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
StringTokenizer st2 = new StringTokenizer(br.readLine());
L = new int[N + 1];
J = new int[N + 1];
dp = new int[N + 1][max + 1];
for (int i = 1; i <= N; i++) {
L[i] = Integer.parseInt(st.nextToken());
J[i] = Integer.parseInt(st2.nextToken());
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= max; j++) {
if (L[i] <= j) {
dp[i][j] = Math.max(dp[i - 1][j - L[i]] + J[i], dp[i - 1][j]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
System.out.print(dp[N][max]);
}
}복잡도
- 시간: O(NW)
- 공간: O(NW)