| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 1105 | 204 | 100 | 21.186% |
문제
윤화와 준희는 솔선수범하여 쓰레기를 줍는 착한 일을 하였다. 원장선생님께서는 윤화와 준희를 칭찬하시고 과자나 사 먹으라고 하시며 동전 몇 개를 윤화와 준희에게 건네 주었다.
그런데 돈을 받은 윤화와 준희는 좋아하기보다 고민에 빠지고 말았다. 원장선생님께 받은 이 돈을 어떻게 나누어 할지 고민에 빠진 것이다. 두 사람 모두 상대방이 자기보다 1원이라도 더 받는 것은 도저히 인정할 수 없어 한다. 따라서 돈을 똑같이 둘로 나누어 가져야 두 사람이 모두 만족할 수 있게 된다.
하지만 두 사람에게 돈을 똑같이 나누는 것이 불가능한 경우도 있다. 예를 들어 500원짜리 1개와 50원짜리 1개를 받았다면, 이 돈을 두 사람이 똑같이 나누어 가질 수는 없다. 물론 동전을 반으로 잘라서 나누어 가질 수도 있겠지만 그러면 돈으로서의 가치를 잃기 때문에 그렇게 할 수는 없다.
이제 우리가 할 일은 다음과 같다. 원장 선생님께서 N가지 종류의 동전을 각각 몇 개씩 주셨을 때, 그 돈을 반으로 나눌 수 있는지 없는지 판단하는 것이다.
입력
세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1≤N≤100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원장선생님께서 주신 금액의 총 합은 100,000원을 넘지 않는다.
출력
첫째 줄부터 세 줄에 걸쳐, 각 입력에 대하여 반으로 나누는 것이 가능하면 1, 불가능하면 0을 출력한다.
접근
간단한 냅색 DP 문제이다.
동전들의 쌍이 (총합 / 2)를 만족시키는 경우가 있는지 찾으면 된다.
돈은 뒤에서부터 순회해야된다는 것만 기억하고 풀면 된다.
풀이
dp table을 모두 0으로 초기화 시킨 뒤, 3중 loop문을 돈다.
coin을 순회하면서 이전에 나온 가장 큰 max_money값부터 0까지 거꾸로 돈을 순회한다.
dp[j]가 1인 경우 동전을 갖고 있는 갯수만큼 반복해가면서 더해주면 된다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int N, dp[50001];
pair<int, int> coin[100];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
FUP(T, 1, 3)
{
int sum = 0, max_money = 0;
MS(dp, 0);
dp[0] = 1;
CIN(N);
FUP(i, 0, N - 1)
{
CIN2(coin[i].first, coin[i].second);
sum += (coin[i].first * coin[i].second);
}
if (sum % 2)
{
COUT("0\n");
continue;
}
sum /= 2;
FUP(i, 0, N - 1)
{
FDOWN(j, max_money, 0)
{
if (dp[j])
{
FUP(k, 1, coin[i].second)
{
int l = j + coin[i].first * k;
if (l > sum) break;
dp[l] = 1;
max_money = max(max_money, l);
}
}
}
}
COUT(dp[sum]);
ENDL;
}
return 0;
}