5215번 : 햄버거 다이어트 [Java]

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

SW Expert Academy

 

해결 방식 고민

 

1. 재료들을 고를 수 있는 모든 부분집합을 고른 후, 각 부분집합이 완성될 때마다 칼로리의 합과 맛에 대한 점수의 합을 확인.

2. 함수에서 맛 점수 합과 칼로리 합을 가지고 다니며 확인.

 

=> 2번 방식은 모든 경우를 확인하지 않아도 되기 때문에 시간 절약 가능

 

 

해결 방안

 

배열에서의 순서 확인을 위한 idx와 맛 점수 합을 위한 sumt, 칼로리 합을 위한 sumc를 사용.

hamburger(idx + 1, sumt + score[idx], sumc + cal[idx]);

 : 재료를 선택했다면 해당 재료의 맛점수와 칼로리를 더해주고 다음 idx로.
hamburger(idx + 1, sumt, sumc);

 : 재료를 선택하지 않았다면 다음 idx로.

 

 

전체코드

import java.util.Scanner;

public class Solution {
	static int N, L;
	static int[] score;
	static int[] cal;
	static int ans;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt(); // 재료의 수
			L = sc.nextInt(); // 제한 칼로리
			score = new int[N];
			cal = new int[N];

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

			hamburger(0, 0, 0);

			System.out.println("#" + tc + " " + ans);
		}
	}

	private static void hamburger(int idx, int sumt, int sumc) {

		if (sumc > L)
			return;
		if (idx == N) {
			if (sumt > ans) {
				ans = sumt;
			}
			return;
		}

		hamburger(idx + 1, sumt + score[idx], sumc + cal[idx]);
		hamburger(idx + 1, sumt, sumc);
	}
}