https://www.acmicpc.net/problem/1535
1535번: 안녕
첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번
www.acmicpc.net
코드설명
냅색(배낭, Knapsack) + DP(Dynamic Programming)문제입니다.
문제는 냅색 배낭 알고리즘입니다.
N의 범위가 작기때문에 DFS를 활용하여 해결했습니다.
문제에는 DP없이 사용하여도 해결할 수 있지만, N이 커진다면 어떻게 될까 하여 DP를 같이 적용해보았습니다.
코드
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);
}
}
}