[SWEA] 5215 햄버거 다이어트 D3 - 자바(Java)/ 중복조합, DFS, DP

📑 문제

 

SW Expert Academy

문제

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

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

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

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

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

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

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

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

 

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
 

각 테스트 케이스의 첫 번째 줄에는 재료의 수, 제한 칼로리를 나타내는 N, L(1 ≤ N ≤ 20, 1 ≤ L ≤ 104)가 공백으로 구분되어 주어진다.
 

다음 N개의 줄에는 재료에 대한 민기의 맛에 대한 점수와 칼로리를 나타내는 Ti, Ki(1 ≤ Ti ≤ 103, 1 ≤ Ki ≤ 103)가 공백으로 구분되어 주어진다.

 

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 주어진 제한 칼로리 이하의 조합중에서 가장 맛에 대한 점수가 높은 햄버거의 점수를 출력한다.

 

입력

1 5 1000 100 200 300 500 250 300 500 1000 400 400

//Test Case 갯수 //Test Case #1, N = 5, L = 1000 //Test Case #1, 첫번째 재료 정보

 

출력

#1 750

//Test Case #1의 정답

 

 

 

 

 

 

 

✒️ 풀이

 DFS로 조합 코드를 짜서 푸는 법과, DP를 이용하는 방법 두 가지가 있다.

 나는 조합을 연습하기에는 요 문제가 최고 짱짱이라고 생각하는데, DP 연습으로도 좋은듯..?

 

 💡 DFS로 풀기

 조합을 풀고 싶으면 이 문제를 풀면 된다! 싸피에서 조합으로 들어갈 때 이 문제부터 풀자고 했다 (ㅋㅋ)

 햄버거 재료를 어떻게 조합할지 선택하면 된다. 

 문제를 정리하자면 아래와 같다.

 

 1. 특정 재료를 선택할 수도 있고, 선택 안할 수도 있다. => 조합

 2. 같은 재료를 여러 번 사용할 수 없다 => 중복조합이 아님

 3. 만든 조합이 칼로리 제한을 넘으면 안된다 => DFS문을 빠져나올 조건문

 4. 조합한 재료들의 선호도 합이 제일 큰 것을 찾아야 한다 => 조합을 마칠 때마다 체크

 

 위 조건에 맞게 DFS 코드를 짜야 하는데, 자세한 설명은 코드에 주석으로 첨부하겠다.

 

 

 

💡 DP로 풀기

 저는 아직 DP를 풀지 못해서.....싸피 당시 동기 분의 코드 살짝 바꿔둔걸 첨부한 것으로 대체하겠습니다(^^)

 풀 줄 아는 분들은 아래 코드 보면 아실 것....

 

 

 

 

 

 

 

 

🙋‍♀️ 의견

 🗓️ 2021.8.11

 풀지 못했다...........언제였지 풀어보라고 했는데 그때도 못풀었다.

 교수님이 이제 문제 몇 개 풀어봤으니 다시 풀어보라고 시간을 주셨는데 또 못풀었다. 이게 어떻게 D3지? D4는 되어야하는 것 아닌가요...

 다들 잘 푸네..ㅠㅠ진짜 너무...자존감이 바닥치는 것 같다. 스트레스가 극치를 찍는다. 도망치고 싶다..

 푸는 방식들이 다 똑같다. DFS처럼 재귀를 사용해서 부분집합을 모두 가본다.

 아!!!! 나 바보네..ㅠㅠㅠㅠ부분집합은 유튜브 라이브 강의에서 순열/조합으로 풀어봤잖아!!!!!!

 햄버거 문제=부분집합이라고 생각이 귀결되질 않았다.

 

🗓️ 글쓰는 현재

 2년 전의 나.....제법 귀여웠군(ㅋㅋ) 🥹

 저 때 나는 코딩테스트라는건 해본 적도 없는데 싸피에 입소해서, 

 👦 (교수님): 여러분들 그럼 이번엔 이 문제를 각자 풀어볼까요~?
 👥 : 네에~!!!

 

 어려워하는 사람 없이 착착착 진행되는 강의에 혼자 적응하지 못했던 기억이 난다.

 나만....이런거 할 줄 몰라? 나만 문제 푸는 법 몰라? 나만 함수 몰라? 나만 알고리즘 몰라?

 ㅋㅋㅋㅋ무한의 물음표 ㅠㅠㅠㅠㅠㅠㅠㅠㅠ

 하지만 다시 생각해봐도 이때 다른 사람들 코드도 보고, 교수님의 풀이를 보았던게 지금의 내게 큰 도움이 되었던 것 같다.

 혼자 이걸 어떻게 하나하나 다 공부해.... 시간도 오래 걸렸을 것이고, 그만큼의 의지력도 안됐을 것이다.

 아무것도 모르던 병아리 입을 강제로 벌려 코드를 넣어줬던 싸피....지금도 사랑해🫶

 

 

 

 

 

 

 

💻 소스코드: 자바(Java)

DFS

public class Solution_SWEA_5215_햄버거다이어트_D3 {
	static int[] taste, cal;
	static int N, L, max;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine()); //테스트케이스

        for (int testCase = 1; testCase <= T; testCase++) {
            st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken());//재료의 수
            L = Integer.parseInt(st.nextToken());//제한 칼로리

            taste = new int[N]; //맛 점수
            cal = new int[N]; //칼로리
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                taste[i] = Integer.parseInt(st.nextToken());
                cal[i] = Integer.parseInt(st.nextToken());
            }//end of input

            max = 0;
            getSubSet(0, 0, 0);

            sb.append("#").append(testCase).append(" ").append(max).append("\n");
        }
        System.out.print(sb);
    }

    private static void getSubSet(int cnt, int calSum, int tasteSum) { //재료 부분집합 구하기
        if (calSum > L) return; //최대 칼로리 초과하면 돌아가기
        if (cnt == N) {
        	// 마지막 재료까지 확인했으면(조합으로 포함했든 안했든) DFS에서 빠져나온다
            // 그 전에 지금까지 조합의 칼로리 합이 최대를 넘지 않았으면, max값을 갱신한다.
        	if(calSum <= L) max = Math.max(max, tasteSum);
            return; 
		}
        
        //해당 재료 선택했을 때
        getSubSet(cnt + 1, calSum + cal[cnt], tasteSum + taste[cnt]);

        //해당 재료 선택하지 않았을 때
        getSubSet(cnt + 1, calSum, tasteSum);
    }
}

 

 

DP

public static void main(String[] args) throws Exception {
	BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
	int tc= Integer.parseInt(br.readLine());
	StringBuilder sb= new StringBuilder();
	for(int t= 1; t<= tc ;t++) {
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int n = Integer.parseInt(st.nextToken()); //재료의 수
		int l = Integer.parseInt(st.nextToken()); //제한 칼로리
		int[] T = new int[n+1];
		int[] K = new int[n+1];
		for(int i=1;i<=n;i++) {
			StringTokenizer st1 = new StringTokenizer(br.readLine()," ");
			T[i]=Integer.parseInt(st1.nextToken());
			K[i]=Integer.parseInt(st1.nextToken());
		}
		
		int[][] dp=new int[n+1][l+1];
		
		for(int i=1;i<=n;i++) {
			for(int j=0;j<=l;j++) {
			if(j<K[i]) {
					dp[i][j]=dp[i-1][j];
				}
				else {
					dp[i][j]=Math.max(dp[i-1][j-K[i]]+T[i], dp[i-1][j]);
				}
			}
		}	
		sb.append("#").append(t).append(" ").append(dp[n][l]).append("\n");
	}
	
	System.out.print(sb);
}

 

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

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