[Java] SWEA5215_ 햄버거다이어트

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT 

SW Expert Academy

[문제]

평소 햄버거를 좋아하던 민기는 최근 부쩍 늘어난 살 때문에 걱정이 많다.

그렇다고 햄버거를 포기할 수 없었던 민기는 햄버거의 맛은 최대한 유지하면서 정해진 칼로리를 넘지 않는 햄버거를 주문하여 먹으려고 한다.

민기가 주로 이용하는 햄버거 가게에서는 고객이 원하는 조합으로 햄버거를 만들어서 준다.

하지만 재료는 미리 만들어서 준비해놓기 때문에 조합에 들어가는 재료를 잘라서 조합해주지는 않고, 재료를 선택하면 준비해놓은 재료를 그대로 사용하여 조합해준다. 

민기는 이 가게에서 자신이 먹었던 햄버거의 재료에 대한 맛을 자신의 오랜 경험을 통해 점수를 매겨놓았다.

민기의 햄버거 재료에 대한 점수와 가게에서 제공하는 재료에 대한 칼로리가 주어졌을 때,

민기가 좋아하는 햄버거를 먹으면서도 다이어트에 성공할 수 있도록 정해진 칼로리 이하의 조합 중에서 민기가 가장 선호하는 햄버거를 조합해주는 프로그램을 만들어보자.

(단 여러 재료를 조합하였을 햄버거의 선호도는 조합된 재료들의 맛에 대한 점수의 합으로 결정되고, 같은 재료를 여러 번 사용할 수 없으며, 햄버거의 조합의 제한은 칼로리를 제외하고는 없다.)

 

[입력]

1               //테스트케이스
5 1000        // 재료수, 제한칼로리
100 200      //재료1의 맛 , 칼로리
300 500
250 300
500 1000
400 400

 

[출력]

#1 750

 

[풀이]

조건 1. 재료 수는 상관없음

조건 2. 제한된 칼로리가 넘지않는것  

조건 3. 최상의 맛

=> 부분집합

순열과 조합은 nPr, nCr 과 같이 n개중에서 r개를 뽑는것

이번 문제에서는 재료수가 정해지지 않았으므로 부분집합으로 푸는것이 맞다. 

모든 재료에 대해서 뽑는 경우와 뽑지않는경우를 재귀를 통해 구현하였다.

 

정리해놓았던 부분집합 기본코드를 활용하여 풀어보았다.

https://java-is-happy-things.tistory.com/8

[Java] 부분집합

 

import java.util.Arrays;
import java.util.Scanner;

public class SWEA5215_burgerdiet {
	static int N, likcal, maxjumsu;
	static int[] jumsu, kcal;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int tc = sc.nextInt();
		for (int t = 0; t < tc; t++) {
			maxjumsu =0;
			N = sc.nextInt();
			likcal = sc.nextInt();

			jumsu = new int[N];
			kcal = new int[N];

			for (int i = 0; i < N; i++) {
				jumsu[i] = sc.nextInt();
				kcal[i] = sc.nextInt();
			}

			combination(0, 0, 0);
			System.out.printf("#%d %d\n", t+1, maxjumsu);
		}
	}

	private static void combination(int cnt, int j, int k) {	//인덱스, 점수의 합, 칼로리의 합

		if (k > likcal)	//리미트칼로리 넘으면 끝(조건2)
			return;
		if (cnt == N) {
			if (j > maxjumsu) {
				maxjumsu = j; // 현재 점수누적합이 max보다 크면 max변경(조건3)
			}
			return;
		}

		combination(cnt + 1, j + jumsu[cnt], k + kcal[cnt]);	//선택하는 경우 
		combination(cnt + 1, j, k);	//선택하지 않는 경우
	}
}

 

햄버거로 다이어트 할 수 있으면 나도 맨날 햄버거만 먹을래 !

---

 

2022.04.05 수정

Knapsack알고리즘을 이용한 풀이방법

 

2차원배열 이용

package day20.ws;

import java.util.Arrays;
import java.util.Scanner;

public class SWEA5215_burgerdiet_DP {
	static int N, likcal;
	static int[] jumsu, kcal;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int tc = sc.nextInt();
		for (int t = 0; t < tc; t++) {
			N = sc.nextInt();
			likcal = sc.nextInt();

			jumsu = new int[N + 1];
			kcal = new int[N + 1];
			int[][] results = new int[N + 1][likcal + 1];

			for (int i = 1; i <= N; i++) {
				jumsu[i] = sc.nextInt();
				kcal[i] = sc.nextInt();
			}
			int curjumsu = 0, curkcal = 0;
			for (int item = 1; item <= N; item++) {
				curjumsu = jumsu[item]; // 현 아이템의 점수
				curkcal = kcal[item]; // 현 아이템의 칼로리

				for (int kcal = 1; kcal <= likcal; kcal++) {
					if (curkcal <= kcal) {	
						//현재 칼로리가 작거나 같다면 1.선택X(같은무게 이전테이블) 
						//					 2.선택 O(지금가치 + 지금무게를 뺀 이전item) 중 큰 가치
						results[item][kcal] = Math.max(results[item - 1][kcal],
								curjumsu + results[item - 1][kcal - curkcal]);
						//현재칼로리가 크면 선택X (이전 아이템의 가치)
					} else {
						results[item][kcal] = results[item - 1][kcal];
					}
				}
			}

			System.out.println(results[N][likcal]);
			sc.close();
		}
	}

}

1차원배열 이용

package day21.ws;

import java.util.Arrays;
import java.util.Scanner;

public class SWEA5215_burgerdiet_DP_1 {
	static int N, L;
	static int[] jumsu, kcal;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int tc = sc.nextInt();
		for (int t = 0; t < tc; t++) {
			N = sc.nextInt();
			L = sc.nextInt() / 100;

			jumsu = new int[N + 1];
			kcal = new int[N + 1];
			int[] results = new int[L + 1];

			for (int i = 1; i <= N; i++) {
				jumsu[i] = sc.nextInt();
				kcal[i] = sc.nextInt() / 100;
			}
			for (int i = 1; i <= N; i++) {			// 첫번째 음식재료부터~
				for (int k = L; k>=kcal[i]; k--) {		//뒤에서 부터 넣을수 있는지 확인 (제한칼로리까지만)
					
					//안넣거나 vs 지금 넣고 칼로리 뺀만큼의 기존 누적점수 중 큰 값
				results[k]=Math.max(results[k], jumsu[i]+results[k-kcal[i]]);		
				}
				
			}

		System.out.println("#" + (t+1) + " " + results[L]);
		sc.close();
		}
	}

	
}

https://java-is-happy-things.tistory.com/30

Knapsack알고리즘