Featured image for [알고리즘] 5215. 햄버거 다이어트

[알고리즘] 5215. 햄버거 다이어트

작성자:

0. 문제

SW Expert Academy

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

SW Expert Academy

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

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

1. C++

가. 제출

#include<iostream>
#include<algorithm>

using namespace std;

const int MAXN = 20;
int n, l, ret;
int t[MAXN], k[MAXN];

void solve(int depth, int cal, int score){
    if(depth == n){
        if(cal <= l && score > ret){
            ret = score;
        }
        return;
    }
    if(cal > l) return;
    score += t[depth];
    cal += k[depth];
    solve(depth+1, cal, score);

    score -= t[depth];
    cal -= k[depth];
    solve(depth+1, cal, score);
    return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int T;
    cin >> T;
    for(int tc=1; tc<=T; ++tc){
        ret = 0;
        cin >> n >> l;
        for(int i=0; i<n; ++i){
            cin >> t[i] >> k[i];
        }
        solve(0, 0, 0);
        cout << "#" << tc << " " << ret << '\n';
    }
    return 0;
}
Code language: PHP (php)

재귀함수를 사용해서 모든 조합을 생성해서 비교한다.

단 이미 제한 칼로리를 넘어선 경우는 생략한다.

나. 더 좋은 코드

#include <bits/stdc++.h>

using namespace std;

int n, l;
int dp[21][10001];

int main()
{
    int T;
    cin >> T;

    for (int t = 0; t < T; t++)
    {
        // l = 제한 칼로리
        cin >> n >> l;

        int score[21];
        int cal[21];

        for (int i = 1; i <= n; i++)
        {
            cin >> score[i] >> cal[i];
        }
        for (int i = 1; i <= n ; i++)
        {
            for (int j = 1; j <= l; j++)
            {
                if (cal[i] > j)
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cal[i]] + score[i]);
            }
        }
        cout << "#" << t+1 << " " << dp[n][l] << '\n';
    }

    return 0;
}
Code language: PHP (php)

knapsack 문제라고 한다.

  • j : 지금까지의 누적 칼로리

  • if (cal[i] > j) dp[i][j] = dp[i - 1][j]; : 넣을 수 없을 경우. (추가 후 칼로리 < 추가할 칼로리)

  • else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cal[i]] + score[i]);
    : 재료를 넣을 수 있는 경우. 넣는 것과 넣지 않는 것을 비교한다.
    : dp[i - 1][j - cal[i]] 재료를 넣기 전 점수 (추가 전 칼로리일 때 점수)

  • dp[n][l] : n개의 재료를 l 칼로리 이하로 조합했을 때 최대 점수.

2. Java

import java.util.Scanner;

public class Solution
{
    static final int MAXN = 20;
    static int n, l, ret;
    static int[] t = new int[MAXN]; 
    static int[] k = new int[MAXN];

    public static void solve(int depth, int score, int cal){
        if(depth == n){
            if(cal <= l && score > ret){
                ret = score;
            }
            return;
        }
        if(cal > l) return;

        score+=t[depth];
        cal+=k[depth];
        solve(depth+1, score, cal);

        score-=t[depth];
        cal-=k[depth];
        solve(depth+1, score, cal);
        return;
    }

    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int tc=1; tc <= T; tc++){
            ret = 0;
            n = sc.nextInt();
            l = sc.nextInt();

            for(int i=0; i<n; i++){
                t[i] = sc.nextInt();
                k[i] = sc.nextInt();
            }

            solve(0,0,0);
            System.out.println("#" + tc + " " + ret);
        }
        sc.close();
    }
}
Code language: PHP (php)

(240203 추가)

Java 재귀로 풀어봄.

import java.io.*;
import java.util.StringTokenizer;

public class SWEA5215 {

	static int n , l, ret;
	static int[] cals, scores; //칼로리, 점수를 저장하는 배열

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

		int T = Integer.parseInt(st.nextToken());
		for(int tc=1; tc<=T; tc++) {
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			l = Integer.parseInt(st.nextToken());
			ret = 0;
			
			//입력
			scores = new int[n];
			cals = new int[n];
			for(int i=0; i<n; i++) {
				st = new StringTokenizer(br.readLine());
				scores[i] = Integer.parseInt(st.nextToken());
				cals[i] = Integer.parseInt(st.nextToken());
			}
			
			solve(0, 0, 0);
			
			//조건을 만족하는 최대 점수 출력
			System.out.printf("#%d %d%n", tc, ret);
			
		}
		br.close();
	}
	
	public static void solve(int depth, int calSum, int scoreSum) {
		if(calSum > l) return; //가지치기
		if(depth == n) {
			//if(calSum > l) return; // 제한 칼로리보다 이하만 가능.
			ret=Math.max(ret, scoreSum);
			return;
		}
		
		//포함
		solve(depth+1, calSum+cals[depth], scoreSum + scores[depth]);
		//미포함
		solve(depth+1, calSum, scoreSum);
	}

}
Code language: JavaScript (javascript)

 

댓글 남기기