[부분집합] SWEA 5215번 햄버거 다이어트 - JAVA

 

 

 

 

---

1. 문제 출처

---

 

SW Expert Academy

 

 

 

---

2. 설계

---

 

다이어트를 위해 제한 칼로리 이하의 재료를 조합해 가장 높은 맛 점수를 가진 햄버거를 만드는 것이 목표이다. 그래서 1번 재료, 2번 재료, 3번 재료 등 다양한 재료를 가지고 어떤 재료를 선택하고, 어떤 재료를 선택안할 것인지를 고려해 햄버거를 만드는 것이 포인트이다.

 

 

우선 햄버거의 재료는 다음과 같이 정해진다.

1) 같은 재료를 2번 넣을 수는 없다.

2) 1번 재료 + 2번 재료 + 3번 재료 = 3번 재료 + 1번 재료+ 2번 재료의 조합은 같은 것이므로 순서는 중요하지 않다.

 

때문에 이 문제는 POWER SET, 즉 부분 집합으로 푼다. 부분 집합에 대한 설명은 아래에서 확인할 수 있다.

 

https://tksgk2598.tistory.com/183

부분집합 / 조합 / 순열 / NEXT PERMUTATION 총정리

 

 

[햄버거 다이어트 부분집합 함수]

public static void powerSet(int depth, int score, int calory) {
		//칼로리가 제한 칼로리보다 작으면 높은 점수 갱신
		if(calory<=C) {
			result=Math.max(score, result);
		}
		
		//칼로리가 제한 칼로리를 넘으면 그만!
		if(calory>C) return;
		
		if(depth == N) return; //모든 재료 고려 해줬다.
		
		//이 재료 선택
		powerSet(depth+1,score+InList[depth].score, calory+InList[depth].calory);
		
		//이 재료 선택 안함
		powerSet(depth+1,score, calory);
		
	}

부분 집합 함수를 보면 현재 depth번째의 재료를 선택할 때 선택지는 2가지이다. 이 재료를 선택을 할 것인가 말 것인가.

 

때문에 이 재료를 선택한다면, 그 다음 재료를 선택할지 말지 고려하기 위해 depth+1을 넘겨주고, 이 재료의 점수(score)와 칼로리(calory)를 전달해준다.

 

이 재료를 선택한 경우를 계속 확인하면서 가능한 경우를 모두 확인하다가 제한된 칼로리가 넘으면 그만두고, 그렇지 않으면 계속해서 맛 점수가 최대인지 비교해서 갱신해준다.

 

또한 depth(재료 수를 의미)의 차원이 재료 갯수를 넘어버리는 것은 의미가 없기 때문에 그만둔다.

 

 

 

---

3. 전체코드

---

 

package SWEA5215;

import java.util.Scanner;

public class 햄버거다이어트 {
	static Ingredient[] InList;//재료리스트
	static int N,C;
	static int result;//높은 점수 저장
	static class Ingredient{
		int score;
		int calory;
		public Ingredient(int score, int calory) {
			super();
			this.score = score;
			this.calory = calory;
		}
		
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();//test case 
		
		for(int T = 1;T<t+1;T++) {
			N = sc.nextInt();//재료 갯수
			C = sc.nextInt();//제한 칼로리
			
			//재료 갯수만큼 정보 받기
			InList = new Ingredient[N];
			for(int i=0;i<N;i++) {
				//점수와 칼로리 넣기
				InList[i]=new Ingredient(sc.nextInt(),sc.nextInt());
			}
			
			//입력 끝
			
			powerSet(0,0,0); //만족도 높은 햄버거 만들기
			
			System.out.println("#"+T+" "+result);//결과 출력
			
			result=0;//초기화
			
			
		}//test case end
	}

	/**
	 * 같은 재료 뽑으면 안됨 = 중복안됨
	 * 순서는 중요하지 않다. 1,3,5번 재료나 3,5,1번 재료나 같다.
	 * => 부분집합
	 * */
	
	public static void powerSet(int depth, int score, int calory) {
		//칼로리가 제한 칼로리보다 작으면 높은 점수 갱신
		if(calory<=C) {
			result=Math.max(score, result);
		}
		
		//칼로리가 제한 칼로리를 넘으면 그만!
		if(calory>C) return;
		
		if(depth == N) return; //모든 재료 고려 해줬다.
		
		//이 재료 선택
		powerSet(depth+1,score+InList[depth].score, calory+InList[depth].calory);
		
		//이 재료 선택 안함
		powerSet(depth+1,score, calory);
		
	}
}

 

 

---

햄버거 다이어트 복습 끝!

부분 집합 아직 잊지 않았다고~