Boj 10982) 행운쿠키 제작소

문제

백준 10982

설명

배낭문제(Knapsack Problem) 을 약간 변형시킨 문제임.(평범한 배낭 문제)

우선 어차피 쿠키를 오븐 둘 중 하나에 넣어야하며, 넣는 순서가 상관이 없음.

오븐을 편의상 A, B 라고 부르겠음.

아이디어

• A, B 오븐이 있다고 하면, A 오븐이 x 초 돌려야 할 때, B 오븐을 최소 y 초 돌려야 한다는 것을 dp[x] = y 라고 표현하겠음.
• i 번째 쿠키를 추가로 계산한다고 하면 dp[x] = min(dp[x] + cookies[i].B, dp[x - cookies[i].A]) 로 표현할 수 있음
  • 왜냐하면 ith 쿠키를 A, B 둘중 하나에는 돌려야하기 때문임.
  • 만약 x - cookies[i].A < 0 이면 경우는 하나로 dp[x] = dp[x] + cookies[i].B 가 됨
• 이렇게 모든 쿠키를 계산한 후의 max(i, dp[i]) 는 A, B 에서 돌아가는 시간 중 최댓값이 됨
  • 이 값중 최솟값이 정답임.

시간 복잡도

O(N * 100001)

코드

pair<int, int> cookies[1001];
int dp[100001];

int main()
{
	int t, n, ans;
	cin >> t;
	while (t--)
	{
		fill(dp, dp + 100001, 0);
		
		cin >> n;
		for (int i = 0; i < n; i++)
			cin >> cookies[i].first >> cookies[i].second;
		
		int sum = 0;
		for (int i = 0; i < n; i++)
		{
			sum += cookies[i].first;
			for (int j = sum; j >= 0; j--)
			{
				if (j - cookies[i].first >= 0)
					dp[j] = min(dp[j] + cookies[i].second, dp[j - cookies[i].first]);
				else dp[j] += cookies[i].second;
			}
		}
		ans = numeric_limits<int>::max();
	
		for (int i = sum; i >= 0; i--)
			ans = min(ans, max(dp[i],i));
	
		cout << ans << '\n';
	}
}