백준 1943번, 동전 분배 풀이

문제

백준 1943번

풀이

$ dp[i] = i $원일 때 가진 동전으로 $i$원으로 만들 수 있으면 1, 없으면 0으로 점화식을 세워줍니다.

 

동전의 합이 $ sum $일 때, 두 명에게 같은 돈으로 나눌 수 있는지 없는지는 $dp[sum/2]$가 1인지 확인하면 됩니다. 

$sum$이 홀수인 경우 어떤 식으로 나눠도 홀/짝, 짝/홀로 나눠지므로 두 명에게 같은 돈으로 나눌 수 없습니다.

 

구하고자 하는 것은 $sum/2$의 값으로 문제에서 $sum$의 범위가 $100,000$으로 주어졌으므로 DP table의 크기는 $ 50,000 (+1) $으로 잡아야 합니다.

 

DP table을 채우기 위해서 $50,000$부터 $a$까지 내려가면서 $dp[i - a]$의 값이 1이라면 $dp[i],\ dp[i + a],\ ...,\ dp[i + a * (b-1)]$을 모두 채워주면 됩니다. (단, $a$는 동전의 금액, $b$는 동전의 갯수)

 

이 때, 바텀업을 사용하여 0부터 보게 된다면 1원 하나로 모든 dp table을 다 채울 수 있으니 사용하면 안됩니다.

소스코드

#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef unordered_map<int, int> mpii;

const int MX = 50000;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int T = 3;
	while (T--) {
		int n, sum = 0;
		cin >> n;
		vpii vec(n);
		vi dp(MX + 1);
		for (auto &[a, b] : vec) cin >> a >> b;

		dp[0] = 1;
		for (const auto &[a, b] : vec) {
			for (int j = MX; j >= a; j--)
				if (dp[j - a])
					for (int i = 0; i < b && j + a * i <= MX; i++) dp[j + a * i] = 1;

			sum += a * b;
		}

		cout << (!(sum % 2) && dp[sum / 2]) << "\n";
	}
}