[BAE/<JOON> 문제풀이] 1943. 동전 분배

https://www.acmicpc.net/problem/1943

1943번: 동전 분배

 

핵심::

제한된 동전 개수 세기를 만족하면서 복잡도가 O(N^2) 안인 구현하기

 

풀이::

우선 동전의 전체 가치가 홀수라면 동일하게 나눌 수 없으므로 시작전에 거른다.

 

남은 동전들로 전체 가치의 1 / 2 양을 채울 수 있다면 동일하게 나눌 수 있는 것으로 판단한다. 

 

평소에 보통 동전 개수가 제한된 문제를 풀 때 동전의 개수만큼 해당 가치의 동전을 넣어서 0/1 Knapsack 문제를

 

풀듯이 구현해왔었다. 이 문제에서는 1원짜리 동전이 최대 100000개까지 가능하므로 메모리 제한을 벗어난다. 

 

또한 동전의 갯수만큼 j for 문을 반복하는 방법이 있는데 이 방법은 1 100000 처럼 동전의 갯수가 큰 입력을 통과하지 못한다. ( 열받게 채점률 100%에서 TLE 뜬다 ).

 

따라서 제한된 동전 개수를 세면서 배낭을 채울 수 있는 새로운 구현을 고민해야 했다.

 

아이디어::

이 문제에서는 일반적인 배낭문제 처럼 최소 동전 개수라든가 최대 동전 개수같은 조건을 요구하지 않고 

 

오직 배낭 채우기 가능 여부만 묻고 있다. 따라서 DP 배열에 들어갈 데이터가 사실 0 / 1 인 셈이다.

 

이 공간에 0 / 1이 아니라 사용한 현재 동전 개수를 저장한다면 O(N^2)의 복잡도로 일반적인 배낭문제와 같은 시간복잡도를 가진 코드를 만들 수 있다.

 

코드::

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct coin {
	int val, cnt;
};

bool cmp(coin a, coin b) {
	return a.val < b.val;
}

int main()
{
	int tc;
	tc = 3;
	while (tc--) {
		int sum = 0;
		int n;
		cin >> n;
		vector<coin> arr;
		arr.push_back({ 0, 0 });
		for (int i = 1; i <= n; i++) {
			int c, cnt;
			cin >> c >> cnt;
			arr.push_back({ c, cnt });
			sum += c * cnt;
		}

		if (sum % 2 == 1) {
			cout << 0 << "\n";
			continue;
		}

		sum /= 2;

		sort(arr.begin(), arr.end(), cmp);

		vector<vector<int>> dp = vector<vector<int>>(n + 1, vector<int>(sum + 1));

		for (int i = 1; i <= n; i++) {
			dp[i][0] = 1;
			if (arr[i].val > sum) break;
			for (int j = 1; j <= sum; j++) {
				dp[i][j] = dp[i - 1][j] > 0 ? 1 : 0;
			}
			for (int j = arr[i].val; j <= sum; j++) {
				if (dp[i][j - arr[i].val] > 0 && dp[i][j - arr[i].val] <= arr[i].cnt && dp[i][j] == 0) {
					dp[i][j] = dp[i][j- arr[i].val] + 1;
				}
			}
		}

		cout << (dp[n][sum] > 0 ? 1 : 0) << "\n";
	}

	return 0;
}