[ boj : 17208] 카우버거 알바생

www.acmicpc.net/problem/17208

17208번: 카우버거 알바생

문제 : 치즈버거와 감자튀김이 남았다. 이를 이용해서 최대로 많이 주문을 받을 수 있는 수를 구하자

 

해설 : dp는 언제나 어렵습니다....(저에게 ㅠ)

먼저 전 치즈버거와 감자튀김의 변수를 이용하여 2차원 dp테이블로 작성해보려 했습니다. 그러나 문제가 생기는데 바로 '동일한 치즈버거와 감자튀김이 남았을 경우 그 값이 최적의 값이 아니게 됩니다'

그 이유는 주문하는 순서를 고려하고 풀어나가야 되는데 그러지 못하기 때문이죠 ㅠㅠ

 

그래서 3차원 테이블을 사용했습니다.

dp[x][y][cnt] : x개의 치즈버거와 y개의 감자튀김이 남았고 현재 cnt 번호 까지 주문을 했을때 가질 수 있는 최대값

그럼 이제 현재 주문을 선택할 수 있으면 선택하고, 선택하지 않고 다음 주문번호로 넘어가게끔 구현을 해주면 되겠죠

 

#include<bits/stdc++.h>

using namespace std;

int n, m, k;
int dp[301][301][100],visit[100];
vector<pair<int, int>> v;

int solve(int x, int y,int cnt);

int main()
{
	cin >> n >> m >> k;
	v.resize(n);
	for (int i = 0; i < n; i++)
		cin >> v[i].first >> v[i].second;
	memset(dp, -1, sizeof(dp));
	cout<<solve(m, k,0);
	return 0;
}
int solve(int x,int y,int cnt)
{
	int& ret = dp[x][y][cnt];
	if (cnt >= n)return ret = 0;
	if (ret != -1)return ret;

	ret = 0;
	if (x - v[cnt].first >= 0 && y - v[cnt].second >= 0)
		ret = max(ret, solve(x - v[cnt].first, y - v[cnt].second, cnt + 1)+1);
	ret = max(ret, solve(x, y, cnt + 1));
	return ret;
}