[백준 1943] 동전 분배

• 문제 : 1943 동전 분배

• 유형 : DP

• 아이디어 : 금액의 총합이 10만을 넘지 않기 때문에 반으로 나눠지기 위해서는 5만이하의 금액에서 주어진 입력의 총합의 반이 만들어질 수 있는지 확인하면 된다.

• 풀이 : dp테이블은 i원을 만들 수 있는지 여부로 설정하였다. 입력들을 순회하며 i원을 만들 수 있으면 1 없으면 0을 저장한다. 이전 인덱스가 다음 인덱스에 영향을 주기 때문에 탑다운 방식을 사용한다.

• 코드

#include <bits/stdc++.h>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;

int n, t = 3, dp[50001], sum;
pair<int, int> v[101];

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	while (t--) {
		cin >> n;
		sum = 0;
		for (int i = 1; i <= n; i++) {
			cin >> v[i].first >> v[i].second;
			sum += v[i].first * v[i].second;
		}
		memset(dp, 0, sizeof(dp));

		if (sum % 2 == 1) cout << 0 << '\n';
		else {
			dp[0] = 1;
			for (int i = 1; i <= n; i++) {
				for (int j = 50000; j >= v[i].first; j--) {
					if (dp[j - v[i].first]) {
						for (int k = 0; k < v[i].second && j + k * v[i].first <= 50000; k++) {
							dp[j + k * v[i].first] = 1;
						}
					}
				}
			}
			cout << dp[sum / 2] << '\n';
		}
	}

	return 0;
}