https://www.acmicpc.net/problem/1535
1535번: 안녕
첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번
www.acmicpc.net
코드설명
냅색(배낭, Knapsack) + DP(Dynamic Programming)문제입니다.
문제는 냅색 배낭 알고리즘입니다.
N의 범위가 작기때문에 DFS를 활용하여 해결했습니다.
문제에는 DP없이 사용하여도 해결할 수 있지만, N이 커진다면 어떻게 될까 하여 DP를 같이 적용해보았습니다.
이 문제에서 어떻게 냅색이 사용가능할지 확인해보겠습니다.
1. 세준이가 인사를 할때 : 이 경우 인사할 사람은 n-1명 남으며, 추가로 인사할 수 있는 최대 체력은 health - L[n]이 됩니다. 세준이가 인사한 후 기쁨은 J[n]만큼 증가하며, n-1명의 사람과 health - L[n]의 체력을 사용할 수 있는 세준이의 원래 문제가 남습니다.
2. 세준이가 인사하지 않을떄 : 이 경우 인사할 사람은 n-1명 남으며, 추가로 인사할 수 있는 체력은 그대로 health 입니다. 세준이가 인사했을 때의 기쁨도 그대로이며, n-1 명의 사람과 health만큼의 인사를 할 수 있는 체력이 있는 원래 문제가 남습니다.
즉, 각 상황에서 기쁨이 최대인 사람에게 인사를 하면 되며, 두 경우 모두 원래 문제와 같은 유형의 작은 문제가 남습니다.
이걸 재귀로 구현할시 시간복잡도는 O(2^N) 입니다. 각 함수마다 두개씩의 자식 노드를 가지고 있는 재귀 호출 구조라 생각하면 되며, 같은 하위 문제를 반복 계산하는 경우도 찾을 수 있습니다.
다이나믹 프로그래밍을 적용하기 위해서, 인사 후 최대 기쁨을 저장하는 방법을 찾는 것 입니다.이를 위해 값을 결정하는 변수들의 차원만큼의 행렬에 대응하는 배열을 사용합니다.
이 문제에는 세준이의 체력과 인사할 사람, 두 개의 변수가 있습니다. 각 행이 인사할 사람을 나타내고, 각 열이 체력을 나타내는 행렬을 생각해봅시다. 이 경우 각 행렬의 셀 (r, c)는 사람들 중 r번쨰까지의 사람에게 인사했을 때 체력 c인 상태에서의 최대 기쁨을 저장하면 됩니다. 이 행렬에는 물건이 0개일 때와 체력이 0일떄의 값도 저장해야 하므로, 행렬에 대응하는 배열은 아래와 같이 선언해야합니다.
int cache[N+1][100+1]셀 (r,c)의 값, 즉 체력의 용량이 100이고 i번쟤 사람에까지의 최대 기쁨은 다음 둘 가운데 큰 값입니다.
1. i번째 사람에게 인사하지 않았을 때의 최대 기쁨 : cache[r - 1][c]
2. i번째 사람에게 인사했을 때의 최대 기쁨 : J[r-1] + cache[r - 1][c-L[r - 1]]
이 됩니다.
사람 r을 인사하려면, 체력에는 c - L[r-1]의 체력만 들어있어야 하므로 사람 r의 가격에 이미 계산한 cache[r-1][c-L[r-1]]의 값을 더하면 됩니다.
이를 활용하여 바텀업 방식의 다이나믹 프로그래밍으로 세준이가 인사할 수 있는 최대의 기쁨을 계산합니다.
package Main;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, M, K;
static int answer = 0;
static int[] energy, happy;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
energy = new int[N];
happy = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0; i<energy.length; i++) {
energy[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int i=0; i<energy.length; i++) {
happy[i] = Integer.parseInt(st.nextToken());
}
int[][] cache = new int[N+1][101];
for(int r=0; r<N; r++) {
cache[r][0] = 0;
}
for(int c = 0; c < 101; c ++) {
cache[0][c]=0;
}
for(int i=1; i<=N; i++) {
for(int j=1; j<=100; j++) {
//i번째 사람에게 인사를 하지 않을경우
int ret = cache[i-1][j];
int ret2 = 0;
if(j - energy[i-1] > 0)
ret2 = happy[i-1] + cache[i-1][j - energy[i-1]];
cache[i][j] = Math.max(ret, ret2);
}
}
answer = cache[N][100];
System.out.println(answer);
}
}위와 같이 접근한다면 시간복잡도는 O(100 * N)으로 계산할 수 있습니다.
만약 역추적할경우
package Main;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static int N, M, K;
static int answer = 0;
static int[] energy, happy;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
energy = new int[N];
happy = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0; i<energy.length; i++) {
energy[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int i=0; i<energy.length; i++) {
happy[i] = Integer.parseInt(st.nextToken());
}
int[][] cache = new int[N+1][101];
for(int r=0; r<N; r++) {
cache[r][0] = 0;
}
for(int c = 0; c < 101; c ++) {
cache[0][c]=0;
}
for(int i=1; i<=N; i++) {
for(int j=1; j<=100; j++) {
//i번째 사람에게 인사를 하지 않을경우
int ret = cache[i-1][j];
int ret2 = 0;
if(j - energy[i-1] > 0)
ret2 = happy[i-1] + cache[i-1][j - energy[i-1]];
cache[i][j] = Math.max(ret, ret2);
}
}
answer = cache[N][100];
int maxEnergy = 100;
for(int i=0; i<N; i++) {
if(cache[i][maxEnergy] == cache[i+1][maxEnergy]) {
}else {
picked.add(i);
maxEnergy -= energy[i];
}
}
for(int v : picked) {
System.out.print(v+" ");
}
System.out.println();
System.out.println(answer);
}
static ArrayList<Integer> picked = new ArrayList<>();
}
만약 위 문제를 그대로 재귀형식으로 바꾼다면,
package Main;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N, M, K;
static int answer = 0;
static int[] energy, happy;
static int[][] cache;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
energy = new int[N];
happy = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0; i<energy.length; i++) {
energy[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int i=0; i<energy.length; i++) {
happy[i] = Integer.parseInt(st.nextToken());
}
cache = new int[N+1][101];
for(int i=0; i<N+1; i++) {
Arrays.fill(cache[i], -1);
}
answer = knapsack(0, 100);
System.out.println(answer);
}
static int knapsack(int peopleIdx, int leftEnergy) {
if(peopleIdx == N) {
return 0;
}
if(cache[peopleIdx][leftEnergy] != -1) return cache[peopleIdx][leftEnergy];
int ret = 0;
if(leftEnergy - energy[peopleIdx] > 0) {
ret = knapsack(peopleIdx + 1, leftEnergy - energy[peopleIdx]) + happy[peopleIdx];
}
ret = Math.max(ret, knapsack(peopleIdx + 1, leftEnergy));
return cache[peopleIdx][leftEnergy] = ret;
}
}
역추적할경우
package Main;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N, M, K;
static int answer = 0;
static int[] energy, happy;
static int[][] cache;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
energy = new int[N];
happy = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0; i<energy.length; i++) {
energy[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int i=0; i<energy.length; i++) {
happy[i] = Integer.parseInt(st.nextToken());
}
cache = new int[N+1][101];
for(int i=0; i<N+1; i++) {
Arrays.fill(cache[i], -1);
}
answer = knapsack(0, 100);
reconstruct(0, 100);
for(int i=0; i<N+1; i++) {
for(int j=0; j<=100; j++) {
System.out.print(cache[i][j]+" ");
}
System.out.println();
}
System.out.println();
for(int v : picked) {
System.out.print(v+" ");
}
System.out.println();
System.out.println(answer);
}
static int knapsack(int peopleIdx, int leftEnergy) {
if(peopleIdx == N) {
return 0;
}
if(cache[peopleIdx][leftEnergy] != -1) return cache[peopleIdx][leftEnergy];
int ret = 0;
if(leftEnergy - energy[peopleIdx] > 0) {
ret = knapsack(peopleIdx + 1, leftEnergy - energy[peopleIdx]) + happy[peopleIdx];
}
ret = Math.max(ret, knapsack(peopleIdx + 1, leftEnergy));
return cache[peopleIdx][leftEnergy] = ret;
}
static ArrayList<Integer> picked = new ArrayList<Integer>();
static void reconstruct(int peopleIdx, int leftEnergy) {
//기저사례: 모든 물건을 다 고려했음
if(peopleIdx == N) {
return ;
}
if(knapsack(peopleIdx, leftEnergy) == knapsack(peopleIdx + 1, leftEnergy)) {
reconstruct(peopleIdx + 1, leftEnergy);
}
else {
picked.add(peopleIdx);
reconstruct(peopleIdx + 1, leftEnergy - energy[peopleIdx]);
}
}
}
코드
simulate에 happy값을 넣어서 계산하지 않고, 계산 도중에 happy 값을 처리합니다.
추가로 DP[level][health] : 해당 level, health에서의 최대 행복값을 저장합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int N, M;
public static int answer = 0;
public static int[][] DP;
public static int[] L; //체력
public static int[] J; //기쁨
public static int health = 100;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
DP = new int[21][101]; //21은 인사해야할 사람의 숫자, 101 세준이의 체력의 최대값을 의미합니다. 그리고 DP값은 기쁨의 최대입니다.
L = new int[N];
J = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
L[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int i=0; i<N;i++) {
J[i] = Integer.parseInt(st.nextToken());
}
answer = simulate(0, 0);
System.out.println(answer);
}
public static int simulate(int level, int healthValue) {
if(DP[level][healthValue] > 0) return DP[level][healthValue];
if(level == N) return 0; //범위를 벗어납니다.
int J1 = 0; //기쁨정도
if(healthValue + L[level] < health) { //만약 최대체력범위 100 미만이라면
J1 = J[level] + simulate(level + 1, healthValue + L[level]); //해당 즐거움을 더하는경우
}
int J2 = simulate(level + 1, healthValue + 0); //해당 경우를 더하지 않은경우
return DP[level][healthValue] = Math.max(J1, J2);
}
}
simulate인자에 level과 health 값을 넣어서 계산합니다.
완전탐색을 통한 로직입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int N, M;
public static Node[] node;
public static int answer = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
node = new Node[N];
for(int i=0;i<N;i++) {
node[i] = new Node();
}
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
int input = Integer.parseInt(st.nextToken());
node[i].health = input;
}
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
int input = Integer.parseInt(st.nextToken());
node[i].happy = input;
}
answer = simulate(0, 100);
System.out.println(answer);
}
public static int simulate(int level, int health) {
if(level >= N) {
return 0;
}
int resultA = 0, resultB = 0;
Node temp = node[level];
if(health - temp.health > 0) {
resultA = temp.happy + simulate(level + 1, health - temp.health);
}
resultB = simulate(level + 1, health);
return Math.max(resultA, resultB);
}
}
class Node{
int health;
int happy;
public Node(int health, int happy) {
this.health = health;
this.happy = happy;
}
public Node() {
}
}
아래의 코드에 DP를 추가해보려고 한 코드이지만, DP[level][health][happy] : 현재 Level에서 해당 Health를 가지고 있을떄 가질 수 있는 최대 행복값을 구해야합니다. (만약 위의 코드와 같이 level, healthValue가 함수의 인자로 들어가 있다면, DP[level][health] 로 처리해야합니다.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int N, M;
public static Node[] node;
public static int answer = 0;
public static int[][][] dp;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
node = new Node[N];
dp = new int[21][100 + 1][20*100 + 1];
for(int i=0;i<N;i++) {
node[i] = new Node();
}
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
int input = Integer.parseInt(st.nextToken());
node[i].health = input;
}
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
int input = Integer.parseInt(st.nextToken());
node[i].happy = input;
}
answer = simulate(0, 100, 0);
System.out.println(answer);
}
public static int simulate(int level, int health, int happy) {
if(dp[level][health][happy] > 0) {
return dp[level][health][happy];
}
if(level >= N || health < 0 ) {
return happy;
}
int resultA = 0, resultB = 0;
Node temp = node[level];
//해당 level의 사람에게 인사하는 경우. ( 체력이 남아있어야한다. 처음에 0 인경우까지 포함했는데 체력이 0 이면 인사를 못합니다. )
if(health - temp.health > 0) {
resultA = simulate(level + 1, health - temp.health, happy + temp.happy);
}
//해당 level의 사람에게 인사하지 않는 경우
resultB = simulate(level + 1, health, happy);
return dp[level][health][happy] = Math.max(resultA, resultB);
}
}
class Node{
int health;
int happy;
public Node(int health, int happy) {
this.health = health;
this.happy = happy;
}
public Node() {
}
}
단순히 완전탐색을 통해서 해결한 코드입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int N, M;
public static Node[] node;
public static int answer = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
node = new Node[N];
for(int i=0;i<N;i++) {
node[i] = new Node();
}
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
int input = Integer.parseInt(st.nextToken());
node[i].health = input;
}
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
int input = Integer.parseInt(st.nextToken());
node[i].happy = input;
}
answer = simulate(0, 100, 0);
System.out.println(answer);
}
public static int simulate(int level, int health, int happy) {
if(level >= N || health < 0 ) {
return happy;
}
int resultA = 0, resultB = 0;
Node temp = node[level];
//해당 level의 사람에게 인사하는 경우. ( 체력이 남아있어야한다. )
if(health - temp.health > 0) {
resultA = simulate(level + 1, health - temp.health, happy + temp.happy);
}
//해당 level의 사람에게 인사하지 않는 경우
resultB = simulate(level + 1, health, happy);
return Math.max(resultA, resultB);
}
}
class Node{
int health;
int happy;
public Node(int health, int happy) {
this.health = health;
this.happy = happy;
}
public Node() {
}
}
메모이제이션을 적용하여 가장 빠른 코드입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static int N, K, M;
private static int answer = 0;
private static int[] arr, L, J;
private static int[][] cache;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
L = new int[N]; J = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N; i++) {
L[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int i=0;i<N; i++) {
J[i] = Integer.parseInt(st.nextToken());
}
cache = new int[101][N];
for(int i=0;i<101; i++) {
Arrays.fill(cache[i], -1);
}
System.out.println(getBestHappy(100, 0));
}
public static int getBestHappy(int energy, int personIdx) {
if(personIdx == N) {
return 0;
}
if(cache[energy][personIdx] != -1) return cache[energy][personIdx];
int ret = 0;
ret = getBestHappy(energy, personIdx + 1);
if(energy - L[personIdx] > 0) {
ret = Math.max(ret, getBestHappy(energy - L[personIdx], personIdx + 1) + J[personIdx]);
}
return cache[energy][personIdx] = ret;
}
}
만약, 내가 인사한 사람들의 최대 선호도와 함께, 인사한 사람들의 실제 목록이 궁금할경우의 코드입니다.
reconstruct 함수를 통해서 실제 어떤 사람들에게 인사하였는지 출력할 수 있습니다.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
private static int N, K, M;
private static int answer = 0;
private static int[] arr, L, J;
private static int[][] cache;
private static ArrayList<Integer> picked = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
L = new int[N]; J = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N; i++) {
L[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int i=0;i<N; i++) {
J[i] = Integer.parseInt(st.nextToken());
}
cache = new int[101][N];
for(int i=0;i<101; i++) {
Arrays.fill(cache[i], -1);
}
System.out.println(getBestHappy(100, 0));
reconstruct(100, 0);
for(int v : picked) {
System.out.print(v+" ");
}
}
public static int getBestHappy(int energy, int personIdx) {
if(personIdx == N) {
return 0;
}
if(cache[energy][personIdx] != -1) return cache[energy][personIdx];
int ret = 0;
ret = getBestHappy(energy, personIdx + 1);
if(energy - L[personIdx] > 0) {
ret = Math.max(ret, getBestHappy(energy - L[personIdx], personIdx + 1) + J[personIdx]);
}
return cache[energy][personIdx] = ret;
}
public static void reconstruct(int energy, int personIdx) {
//기저사례 : 모든 사람들을 다 고려했음.
if(personIdx == N) return ;
//두개의 선택지밖에 없기에 아래와 같이 단순하게 처리할 수 있습니다.
//만약 현재 energy와 personIdx와 energy,personIdx+1 때의 행복도가 같다면,
//해당 사람에게는 인사하지 않았다는 의미입니다. ( 인사한 경우라면 [energy][personIdx]의 값은 달라졌어야하기 때문입니다. )
//만약 둘이 같다면, 인사를 하지 않아서 같습니다. 그러므로 다음 재귀함수로 넘어갑니다.
if(getBestHappy(energy, personIdx) == getBestHappy(energy, personIdx + 1)) {
reconstruct(energy, personIdx + 1);
}
//위의 경우에서 다른 사람에게 인사한 값이 최대값인걸 알았다면,
//해당 사람에게는 인사한 것으로 처리하고, 다음 재귀함수를 계속해서 실행합니다.
else if(energy - L[personIdx] > 0) {
picked.add(personIdx);
reconstruct(energy - L[personIdx], personIdx + 1);
}
}
}