[BOJ/Gold 3] 백준 1943 동전 분배(C++)

문제 링크

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

1943번: 동전 분배

 

문제

윤화와 준희는 솔선수범하여 쓰레기를 줍는 착한 일을 하였다. 원장선생님께서는 윤화와 준희를 칭찬하시고 과자나 사 먹으라고 하시며 동전 몇 개를 윤화와 준희에게 건네 주었다.

그런데 돈을 받은 윤화와 준희는 좋아하기보다 고민에 빠지고 말았다. 원장선생님께 받은 이 돈을 어떻게 나누어 할지 고민에 빠진 것이다. 두 사람 모두 상대방이 자기보다 1원이라도 더 받는 것은 도저히 인정할 수 없어 한다. 따라서 돈을 똑같이 둘로 나누어 가져야 두 사람이 모두 만족할 수 있게 된다.

하지만 두 사람에게 돈을 똑같이 나누는 것이 불가능한 경우도 있다. 예를 들어 500원짜리 1개와 50원짜리 1개를 받았다면, 이 돈을 두 사람이 똑같이 나누어 가질 수는 없다. 물론 동전을 반으로 잘라서 나누어 가질 수도 있겠지만 그러면 돈으로서의 가치를 잃기 때문에 그렇게 할 수는 없다.

이제 우리가 할 일은 다음과 같다. 원장 선생님께서 N가지 종류의 동전을 각각 몇 개씩 주셨을 때, 그 돈을 반으로 나눌 수 있는지 없는지 판단하는 것이다.

입력

세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1 ≤ N ≤ 100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원장선생님께서 주신 금액의 총 합은 100,000원을 넘지 않는다. 동전의 금액과 개수는 자연수이고, 같은 금액을 가진 동전이 두 번 이상 주어지는 경우는 없다.

출력

첫째 줄부터 세 줄에 걸쳐, 각 입력에 대하여 반으로 나누는 것이 가능하면 1, 불가능하면 0을 출력한다.

예제 입력 1

2
500 1
50 1
3
100 2
50 1
10 5
3
1 1
2 1
3 1

예제 출력 1

0
1
1

알고리즘 분류

• 배낭 문제

풀이

원장선생님께서 주시는 동전의 금액의 총합은 최대 100,000원까지이므로, 윤화와 준희는 최대 50,000원까지 가질 수 있다. 따라서, DP[50000]이라는 1차원 배열을 선언한다. DP[i]이 1이라면, 윤화와 준희는 각각 i원씩 나눠가질 수 있다는 뜻이고, 0이라면 i원씩 나눠가지는 것은 불가능하다는 뜻이다. 또한, 금액의 총합이 홀수라면, 어떠한 방법을 써도 정확히 절반의 금액만큼 나눠가질 수 없으므로 무조건 답은 0이 된다.

이제 첫 번째 동전부터 N개의 동전을 탐색하면서, 금액을 50,000원부터 0원까지 탐색한다. i번째 동전의 금액을 a, 개수를 b라고 하자. j원을 탐색하는 경우, j-a가 0 이상이어야 한다. DP[j-a]가 1인 경우, DP[j], DP[j+a], ..., DP[j+a*(b-1)]는 전부 1이 될 수 있다.(단 j+(a*k)가 50000을 초과하면 안 된다.) 이런 식으로 N개의 동전을 탐색하며, 50,000원부터 0원까지 탐색하면서 해당 금액만큼 나눠가질 수 있다면 1을 기록해준다.

처음에는 여기서 썼던 방법대로 하려고 했으나 92%에서 시간이 초과돼서 다른 방법을 찾게 되었다.

[BOJ/Gold 4] 백준 14855 만두 가게 사장 박승원(C++)

마지막으로 금액의 총합의 절반의 금액을 Half라고 했을 때, DP[Half]가 1이라면 윤화와 준희 모두 Half원만큼 나눠가질 수 있다는 뜻이 되므로 1을 출력하고, 0이라면 Half원만큼 나눠가질 수 없다는 뜻이 되므로 0을 출력한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX_N 101
#define MAX_M 50001
#define LL long long
#define INF 1e9

using namespace std;
int N;
pair<int, int> Coin[MAX_N];
int DP[MAX_M];
vector<int> Answer;

void Init() {
	for (int i = 0; i < MAX_M; i++) {
		DP[i] = 0;
	}
	DP[0] = 1;
}

void Settings(int Sum) {
	if (Sum % 2 == 1) {
		Answer.push_back(0);
		return;
	}
	int Half = Sum / 2;
	for (int i = 1; i <= N; i++) {
		for (int j = 50000; j >= 0; j--) {
			if (j - Coin[i].first >= 0) {
				if (DP[j - Coin[i].first] == 1) {
					for (int k = 0; k < Coin[i].second; k++) {
						if (j + Coin[i].first * k < MAX_M) {
							DP[j + Coin[i].first * k] = 1;
						}
					}
				}
			}
		}
	}
	if (DP[Half] == 1) {
		Answer.push_back(1);
		return;
	}
	Answer.push_back(0);
}

void Find_Answer() {
	for (int i = 0; i < Answer.size(); i++) {
		cout << Answer[i] << "\n";
	}
}

void Input() {
	for (int i = 0; i < 3; i++) {
		Init();
		cin >> N;
		int Sum = 0;
		for (int j = 1; j <= N; j++) {
			cin >> Coin[j].first >> Coin[j].second;
			Sum += (Coin[j].first * Coin[j].second);
		}
		Settings(Sum);
	}
}

int main() {
	FASTIO
	Input();
	Find_Answer();

	return 0;
}