이것 저것 &

문제링크:www.acmicpc.net/problem/17208

냅색알고리즘을 아는냐 모르냐에 따라서 체감 난이도가 큰 문제입니다.

우선 배낭여행 알고리즘을 모른다 하시면 아래링크 문제부터 풀어 보세요.

gusdnr69.tistory.com/153 

평범한 배낭문제와 같은 맥락입니다.

하지만 감튀랑 버거 두가지를 함께 고려해주어야 하는 문제입니다.

저는 삼차원 배열을 만들어서 해결했습니다.

dp[i][j][u]  => n번째 손님까지, j개의 버거, u개의 감튀로 최대 몇명의 손님을 받을 수 있는가?

이를 위해서는 삼중 포문을 사용해야 합니다.

//solve
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for (int u = 1; u <= k; u++) {
				if (j >= b[i] && u >= p[i]) 
					dp[i][j][u] = max(dp[i - 1][j][u], dp[i - 1][j - b[i]][u - p[i]] + 1);	
				else
					dp[i][j][u] = dp[i - 1][j][u];
			}
	

평범한 배낭문제와 굉장히 유사합니다.

아래는 전체 정답 코드입니다.

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

int n, m, k;

int dp[101][301][301] = { 0, };
int b[301] = { 0, };
int p[301] = { 0, };

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

	cin >> n >> m >> k;

	for (int i = 1; i <= n; i++) 
		cin >> b[i] >> p[i];

	//solve
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for (int u = 1; u <= k; u++) {
				if (j >= b[i] && u >= p[i]) 
					dp[i][j][u] = max(dp[i - 1][j][u], dp[i - 1][j - b[i]][u - p[i]] + 1);	
				else
					dp[i][j][u] = dp[i - 1][j][u];
			}
	
	cout << dp[n][m][k] << endl;
}

손에 안 익으시다면 배낭여행 알고리즘 문제를 3~4개 푸시면서 다른 문제가 나와도 적용할 수 있게 연습해보세요.