BOJ 2629) c++ 양팔 저울

시간 제한 - 1s

메모리 제한 - 128MB

 

---

풀이

1. 구슬과 추를 활용해 무게를 재는 방법

    1.1) 그림 1을 식으로 나타내면 구슬 + 추a + 추b == 추x + 추y ?로 표현 가능

    1.2) 그림 2를 식으로 나타내면 구슬 == 추x + 추y ?로 표현 가능

    -> 방정식의 성질을 이용해 1.1의 식을 구슬 == 추x + 추y - 추a - 추b와 같이 나타냄으로 두 식을 같게 생각할 수 있음

2. 1번의 추1부터 추n까지의 조합을 이용해 만들 수 있는 무게 중 구슬의 무게가 있으면 비교 가능하다고 판단 가능

입력

추의 수 N, 

N개의 추

구슬의 수 M

M개의 구슬

 

자료구조

dp 테이블을 만들까했지만 추를 이용해 만들 수 있는 무게의 집합을 표현하기에 set 자료구조가 좋다고 판단함

추n-1개의 set을 사용해 추n개의 set을 만들기위해 set<int>형 배열을 사용(set<int>[n])

 

로직

1. 추가 아무것도 없을 경우 표현 가능한 수는 0

2. 첫번째 추를 사용해 조합할 경우, 가능한 경우는 0 - 첫번째 추의 무게, 0 + 첫번째 추의 무게와 해당 추를 사용하지 않을 경우의 0

3. n-1번째 조합을 이용해 n번째 조합을 생성

    -> 구슬 = x - y일 수 있으나, 무게가 음수일 수 없기 때문에 조합되는 값을 절대 값으로 계산 시 0 ~ 15,000 사이의 연산 수행

    -> 로직 상 3^n 의 시간 복잡도를 가지나, set의 특성 상 중복되는 값일 경우 insert가 이루어지지 않음

    최대 15000 * n번의 연산 수행

---

 

코드

#include <set>
#include <iostream>
#include <vector>

using namespace std;

int main() {
	int n, g, input;

	cin >> n;
	vector<set<int> >	setvec(n + 1);
	setvec[0].insert(0);

	for (int i = 1; i <= n; ++i) {
		cin >> input;
		for (auto& it : setvec[i - 1]) {
			setvec[i].insert(it);		// 해당 추를 사용하지 않을 경우
			setvec[i].insert(it + input);	// 해당 추를 구슬의 반대편에 둘 경우
			setvec[i].insert(abs(it - input));	// 해당 추를 구슬과 함께 올릴 경우
		}
	}
	cin >> g;
	while (g--) {
		cin >> input;
		if (setvec.back().find(input) == setvec.back().end())
			cout << "N ";	//	구슬의 무게가 만들어질 수 있는 조합 중에 있는지
		else cout << "Y ";
	}cout << endl;
	return 0;
}

 

시간 복잡도

O(3^n)

 

그냥 냅색처럼 풀 수 있었으나, 자료구조도 좀 다르게 생각하고 해서 재밌게 풀었따 ㅋ