[백준] 1943-동전 분배(C++)

문제링크: https://www.acmicpc.net/problem/1943

1943번: 동전 분배

 

dp문제입니다.

 

접근방식

 

1. 모든 경우의 수를 고려하는 브루트 포스방식은 불가

2. 배낭 알고리즘처럼 n = 1 일때 부터 하나씩 경우의 수를 추가해주는 방식으로 구현 

3. 경우의 수에 대한 갯수가 아니라 단순히 가능, 불가능 여부이기 때문에 직관적으로 구현

 

문제풀이 

 

1. n개만큼 반복하며 i개까지 가지고 있을 때 분배가 가능한지 탐색

j를 top-down방식으로 사용하는 이유는 if문에서 이전 인덱스의 dp값을 참조하며 진행하기 때문이다. 

 

 

 

 

 

정답 코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int dp[50001] = { 0, }, n = 0;
int won, cnt;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int t = 3;
	
	while (t--) {
		int sum = 0;
		vector <pair<int, int>> vec;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> won >> cnt;
			vec.push_back(make_pair(won, cnt));
			sum += won * cnt;
		}
		if (sum % 2 == 1) {
			cout << 0 << endl;
			continue;
		}
		memset(dp, 0, sizeof(dp));
		dp[0] = 1;
		for(int i=0;i<n;i++)
			for (int j = 50000; j >= vec[i].first; j--) {
				if (dp[j - vec[i].first] == 1) {
					for (int k = 0; k < vec[i].second && (j + k*vec[i].first) <= 50000; k++) {
						dp[j + k*vec[i].first] = 1;
					}
				}
			}

		if (dp[sum / 2] == 1) {
			cout << 1 << endl;
		}
		else
			cout << 0 << endl;

	}


	return 0;
}