SWEA - 햄버거 다이어트 (C++)

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

N이 20밖에 안되기 때문에 재귀 방식으로 풀어낼 수도 있다.

 

처음 부터 요소를 살펴보면 두가지 행동이 가능할 것이다. 

아직 제한 칼로리를 넘지 않았음을 깔아두고

1. 이번 재료를 소모하고 지나간다. 

2. 이번 재료를 쓰지 않고 넘어간다.

 

그렇다면 함수는 아주 간단하다.

 

void dfs(int idx, int sum_socre, int sum_cal){
    answer = max(answer, sum_socre);
    //cout << idx << " " << sum_socre << " " << sum_cal << '\n';
    if(sum_cal + vec[idx].second <= L && idx != N)
        dfs(idx + 1, sum_socre + vec[idx].first, sum_cal + vec[idx].second);
    if(sum_cal <= L && idx != N)
        dfs(idx + 1, sum_socre, sum_cal);
}

 

그러나 이 풀이는 근본적으로 잘못될 수 있다. 

만약 

1

20 100

1 1

1 1

.

.

1 1

 

이라면 모든 방식이 가능하기 때문에

 

2^20 - 1번 재귀를 돌아야한다. 그러므로 약 1,048,576 연산이 필요하고 재귀의 특성인 오버헤드를 생각하면 효율적이지 못하다. 그리고 25만 되어도 3천만이 넘어가서 시간초과가 발생할 여지도 있다. 

 

그러므로 이 문제의 정 해는 배낭 문제 이다.

 

배낭 문제는 https://tigerfrom2.tistory.com/192 이 문제에서 설명해놓았다.

 

여기서 weight는 칼로리 value는 맛 점수에 해당하고 정답 코드는 다음과 같다.

 

#include <iostream>
#include <vector>
using namespace std;

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

	int T, N, L;
	cin >> T;

	for (int i = 0; i < T; i++) {
		int dp[21][10001] = { 0, };

		vector<pair<int, int>> ham;
		cin >> N >> L;
		for (int j = 0; j < N; j++) {
			int value;
			int weight;
			cin >> value >> weight;
			ham.push_back({ weight, value });
		}

		for (int j = 1; j <= N; j++) {
			int weight = ham[j - 1].first;
			int value = ham[j - 1].second;

			for (int k = 1; k <= 10000; k++) {
				if (k >= weight) {
					dp[j][k] = max(dp[j - 1][k], dp[j - 1][k - weight] + value);
				}
				else {
					dp[j][k] = dp[j - 1][k];
				}
			}
		}

		cout <<"#" << i + 1 << " " << dp[N][L] << '\n';
	}

}

 

 

dp 방식이 약 10배 빠르다.