도시락이 있고 최소 횟수로 x개 이상의 타코야키와 y개 이상의 타이야키를 고르는 문제

Solution

딱 보니 dp 냄새가 난다. 범위도 300으로 작으니 해볼만 하다고 생각.

dp[i][j][k] = i 인덱스까지 도시락 중에 j 개의 타코야키, k 개의 타이야키를 고르는 최소 가지 수

위처럼 dp를 정의하고 다 돌려주면 된다.

단, j, k 값이 계산 중에 300 범위를 넘어갈 수 있는데, 이는 x, j 중에 최솟값으로 처리하면 된다. x 값이 넘는 j의 경우 어차피 상관 없기 때문.

Source Code

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

int n, x, y;
int a[300], b[300];
int dp[301][301][301];

int solve(int idx, int cx, int cy) {
	if (cx >= x && cy >= y)
	{
		return 0;
	}
	if (idx >= n)
	{
		return 987654321;
	}
	if (dp[idx][min(cx, x)][min(cy, y)] != -1)
	{
		return dp[idx][min(cx, x)][min(cy, y)];
	}

	int ret = 987654321;
	// pick
	ret = min(ret, solve(idx + 1, cx + a[idx], cy + b[idx]) + 1);

	// not pick
	ret = min(ret, solve(idx + 1, cx, cy));

	return dp[idx][min(cx, x)][min(cy, y)] = ret;
}

int main() {
	memset(dp, -1, sizeof(dp));

	cin >> n >> x >> y;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i] >> b[i];
	}

	int ans = solve(0, 0, 0);

	if (ans == 987654321)
	{
		ans = -1;
	}
	cout << ans << endl;
}

ABC_219_D - Strange Lunchbox

Problem link

Problem Summary

Solution

Source Code