[SWEA] 5215. 햄버거 다이어트

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

SW Expert Academy

문제 설명 :  정해진 칼로리 이하의 조합 중에서 민기가 가장 선호하는 햄버거를 조합해주기 조건 :  단 여러 재료를 조합하였을 햄버거의 선호도는 조합된 재료들의 맛에 대한 점수의 합으로 결정되고, 같은 재료를 여러 번 사용할 수 없으며, 햄버거의 조합의 제한은 칼로리를 제외하고는 없다. 문제 풀이 :  조합을 활용하여 모든 경우를 다 탐색한다. 즉 모든 경우를 중복 없이 뽑는다. 제한된 칼로리 이하 중 가장 높은 점수를 선택하면 된다. 점수와 칼로리를 담고 있는 Pair 클래스를 ArrayList를 사용해서 입력을 받는다. 반복문을 통해 nC1 부터 nCr 까지 하는 것이 중요하다. 조합함수는 1부터 이용하기 때문에 인덱스 0부터 시작하는 list와 구분을 잘해줘야한다. 한 번 조합을 뽑을 때마다 sumkcal 변수에 칼로리를 누적하고 sumscore 변수에 점수를 누적하여 제한된 칼로리 이하 중 가장 높은 점수를 구한다.

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

class Solution {
	static int T, N, K, x, maxscore;
	static int[] temp;
	static boolean[] mask;
	static ArrayList<Pair> list;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			K = sc.nextInt();
			temp = new int[N + 1];
			mask = new boolean[N + 1];
			maxscore =  Integer.MIN_VALUE;
			list = new ArrayList();
			for (int i = 0; i < N; i++) {
				int sco = sc.nextInt();
				int kca = sc.nextInt();
				Pair p = new Pair(sco, kca);
				list.add(p);
			}
			temp[0] = 1;
			for (int i = 1; i <= N; i++) {// nCr
				x = i;
				comb(1, 0);
			}
			System.out.println("#"+tc+" "+maxscore);
			
		} // end of testcase
	}

	public static void comb(int start, int depth) {
		if (depth == x) {
			int sumkcal = 0;
			int sumscore = 0;
			
			for (int i = 1; i <= depth; i++) {
				Pair a = list.get(temp[i] - 1);
				sumkcal += a.kcal;
				sumscore += a.score;
			//	System.out.print(temp[i] + " ");
			}

			if (sumkcal <= K) {
				if (sumscore > maxscore) {
					maxscore = sumscore;
				}
			}			

			return;
		}

		for (int i = temp[start - 1]; i <= N; i++) {
			if (mask[i])
				continue;
			temp[start] = i;
			mask[i] = true;
			comb(start + 1, depth + 1);
			mask[i] = false;
		}

	}
}

class Pair {
	int score;
	int kcal;

	Pair(int score, int kcal) {
		this.score = score;
		this.kcal = kcal;

	}
}