[백준 스터디 7주차] 17208번 카우버거 알바생 골드4 - 자바(JAVA) / Knapsack/ 배낭문제

📑 문제

https://www.acmicpc.net/problem/17208

문제

중간고사 종료를 기념해 계획 없이 돈을 쓰던 영석이는 안타깝게도 통장 잔고가 100원도 남지 않게 되었고, 결국 영석이는 카우버거 주방 알바를 하기로 했다. 카우버거는 치즈버거와 감자튀김을 파는 중앙대학교의 유명한 음식점이다.

알바 첫날, 영석이가 주방에 들어선 순간 그는 매우 중요한 사실을 깨달았다. 사실 그는 치즈버거는 물론이고 감자튀김도 만들 줄 모른다는 것이다. 이때 다행히도 주방에는 누군가 만들어둔 치즈버거와 감자튀김이 몇 개 남아있었고, 영석이는 현재 들어온 주문을 이걸 이용해 처리하기로 했다.

모든 주문은 각각 치즈버거 요구 개수와 감자튀김 요구 개수를 의미하는 2개의 정수로 이루어진다. 어떤 주문을 처리하기 위해서는 치즈버거와 감자튀김을 정확히 그 주문에서 요구하는 만큼 써야 한다. 또한 주문이 들어온 순서와 관계없이 원하는 주문을 선택해 처리할 수 있으며, 한번 처리한 주문은 사라지므로 같은 주문을 다시 처리하는 것은 불가능하다.

아쉽게도 주방에 남아있는 것이 많지 않기 때문에 어떤 주문은 처리하지 못할 수도 있다. 최선의 방법으로 주문을 선택해 처리한다면 최대 몇 개의 주문을 처리할 수 있을까?

 

입력

첫째 줄에 주문의 수 N(1 ≤ N ≤ 100), 주방에 남은 치즈버거 개수 M(1 ≤ M ≤ 300), 주방에 남은 감자튀김 개수 K(1 ≤ K ≤ 300)가 주어진다.

둘째 줄부터 N개의 줄에는 주문 내용을 의미하는 두 정수 x, y (1 ≤ x, y ≤ 300)가 주어진다. x는 치즈버거 요구 개수, y는 감자튀김 요구 개수를 나타낸다.

 

출력

주방에 남은 치즈버거와 감자튀김을 사용해 처리할 수 있는 최대 주문 개수를 출력한다.

 

 

 

 

 

 

 

 

✒️ 풀이

 이 놈의 DP! 나는 항상 어려워!!!

 재귀로 풀면 시간초과가 난다. 경험담이다....코드상 문제가 없는데 시간초과라는 것은 즉 DP를 쓰라는 뜻이다.

 DP로 접근하면, 전형적인 냅색 문제이다.

 

 

 💡 knapsack(idx, b, f): 주문번호 idx가 들어왔을 때 b개의 버거, f개의 프라이가 남아있는 경우 처리할 수 있는 최대 주문개수를 리턴.

 💡 DP[idx][b][f]: knapsack에서 리턴하고자 하는 값을 저장하는 메모이제이션 배열

 

 

0: (10,10)

1: (10,50)

2: (20,30)

3: (20,30)

4: (15, 10)

 

 예를 들어 총 100개의 버거와 100개의 프라이가 있을 때, 들어온 주문들의 (버거, 프라이)값이 위와 같다고 생각해보자.

 

 주문 0번을 처리한다면 남은 (버거, 프라이)는 (90,90)이 될 것이다.

 

 주문 1번은 두 개의 기로에 놓인다. 주문을 처리하느냐/ 처리하지 않느냐.

 

 주문 1번을 처리한다면 남는 (버거, 프라이)는 (80,30)으로, 이후 처리할 수 있는 주문의 개수는 2번만 선택하거나/3번만 선택하거나/4번만 선택하거나, 총 1개가 될 것이다. 따라서 knapsack(1,90,90)은 1번 주문처리 1+이후 주문들 최대 처리개수 1을 더해 2가 된다.

 

 주문 1번을 처리하지 않는다면, 들어온 (버거, 프라이)값 (90,90)을 그대로 들고 다음 주문들을 처리하러 간다. 이때 넘긴 (90,90)의 값은 주문 2,3,4번을 모두 받을 수 있는 양이므로, 이후 처리할 수 있는 주문의 개수는 3이 리턴된다. 따라서 knapsack(1,90,90)은 1번 주문처리 0+이후 주문들 최대 처리 개수 3을 더하여 총 3이 된다.

 

 주문 1번은 이 두 가지 상태 중 가장 최대값을 리턴하는 값을 찾아 dp[1][90][90]에 저장하고 이를 리턴한다. 위 예시에서는 3이 될 것이다.

 

 이 리턴값은 고스란히 주문 0번으로 돌아간다.

 앞서 위 예시는 주문 0번을 "처리했을 때"를 가정으로 한 것이었다. 주문 0번은 해당 주문을 처리하지 않은 경우와, (0번 주문 처리 개수 1+이후 주문들 최대 처리 개수 3)인 값 4를 비교하여 그 중 최대값을 저장하게 된다. 

 

 

 

 

 

 

 

 

💻 소스코드: 자바(Java)

public class Main_백준_17208_카우버거알바생_골드IV {
	static int N, M, K, result=Integer.MIN_VALUE;
	static int[][] order;
	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());	//order
		M = Integer.parseInt(st.nextToken());	//burgers
		K = Integer.parseInt(st.nextToken());	//fries
		order = new int[N][2];
		dp = new int[N][301][301];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			order[i][0] = Integer.parseInt(st.nextToken()); //burger
			order[i][1] = Integer.parseInt(st.nextToken()); //fri
		}//input
		
		// 특정 order가 남은 감자튀김으로 처리할 수 있을 때: 주문을 받거나/ 안받거나
//		takeOrder(0, 0, 0, 0); 시간초과
		System.out.println(knapsack(0, M, K));;
	}//end of main
	
	static private void takeOrder(int bSum, int fSum, int idx, int cnt) {
		if(idx==N) {
			result = Math.max(cnt, result);
			return;
		}
		int burger = order[idx][0];
		int fri = order[idx][1];
		if(bSum+burger<=M && fSum+fri<=K) {
			takeOrder(bSum+burger, fSum+fri, idx+1, cnt+1);
		}
		takeOrder(bSum, fSum, idx+1, cnt);
	}//end of takeOrder
	
	static private int knapsack(int idx, int b, int f) {
		
		if(idx==N) return 0;
		
		int burger = order[idx][0];
		int fri = order[idx][1];
		if(dp[idx][b][f] != 0) return dp[idx][b][f];
		
		int orderCnt = knapsack(idx+1, b, f);
		if(burger<=b && fri<=f) {
			orderCnt = Math.max(knapsack(idx+1, b-burger, f-fri)+1, orderCnt);
		}
		return dp[idx][b][f] = orderCnt;
	}//end of knapsack
}//end of class

 

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨