양팔저울 (feat. 백준, 2629번)

양팔저울
https://www.acmicpc.net/problem/2629

2629번: 양팔저울

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
using namespace std;
bool dp[40001], tmp[40001];
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, arr[30], count;
	cin >> N;
	for (register int i = 0; i < N; ++i)
		cin >> arr[i];
	for (register int i = 0, j; i < N; ++i) {
		memset(tmp, false, sizeof(tmp));
		for (j = 0; j < sizeof(dp); ++j)
			if (dp[j]) {
				tmp[abs(j - arr[i])] = true;
				tmp[j + arr[i]] = true;
			}
		dp[arr[i]] = true;
		for (j = 0; j < sizeof(tmp); ++j)
			if (tmp[j])
				dp[j] = tmp[j];
	}
	cin >> count;
	for (register int i = 0, v; i < count; ++i) {
		cin >> v;
		if (dp[v])
			cout << "Y ";
		else
			cout << "N ";
	}
	return 0;
}
// *&)*@*

1. 저울 무게에 대한 dp를 생성합니다.
2. 무게추 하나마다 dp에 적용합니다. dp 전체를 검색하여 만약 true면 해당 dp 인덱스의 +-에 무게추를 추가한 것이므로 true로 변경해 줍니다. (dp[5]가 true 이고 무게추 2g짜리를 추가한다면 dp[3] = dp[7] = true 입니다.)
3. 최종적으로 확인할 무게에 해당되는 dp 인덱스가 true면 'Y' 아니면 'N'을 출력합니다.