[백준] 1535 안녕 - 냅색(배낭, Knapsack) + DP(Dynamic Programming) JAVA

passionfruit200 2023. 11. 5. 17:45

2023. 11. 5. 17:45

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);
    	}
    }
    
    
}

'알고리즘 > KnapSack' 카테고리의 다른 글

[백준] 16493 최대 페이지 수 - 배낭문제(냅색, KnapSack) + 동적계획법(DP, Dynamic Programming) JAVA (0)	2023.11.24
[백준] 7579 앱 - DP(Dynamic Programming) + 배낭문제(냅색, KnapSack) JAVA (0)	2023.11.14
[백준] 2629 양팔저울 - DP(Dynamic Programming) + 냅색(Knapsack, 배낭문제) JAVA (0)	2023.11.02
[백준] 12865 평범한 배낭 - DP(Dynamic Programming) + 배낭문제(냅색, KnapSack) JAVA (0)	2023.08.25
[백준] 1106 호텔 - 배낭문제(Knapsack) + DP(Dynamic Programming) JAVA (0)	2023.08.20

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

passionfruit200