[백준/C++] 양팔저울

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제를 처음 봤을 때, 정말 풀 수 있나? 의문이 들었다.

왜냐하면 아무리 DP로 푼다고 해도, 시간 복잡도는 O(3^n)이 되기 때문이다.  (n은 추의 개수)

 

여기서 3^n인 이유는 아래와 같이 3가지 경우가 존재하기 때문이다.

 

1. 구슬 쪽에 추를 올리는 경우

2. 추를 사용하지 않는 경우

3. 구슬 반대편에 추를 올리는 경우

 

그렇기 때문에 시간 복잡도는 O(3^n)이다.

 

한번 최악의 경우를 상상해 보면 추의 무게가 1, 3, 9 ,27 ... 처럼 3의 배수로 늘어나는 경우이다.

(중복해서 만들어지는 추의 무게가 없는 경우의 예)

 

하지만, 이 문제에는 무게추에 제한사항이 있기 때문에 실제 시간복잡도는 O(3^n)으로 작동하지 않는다.

 

중복되는 수를 만들 수 없는 최악의 경우가 만들어지기 위해서는 추의 무게도 3의 배수로 늘어나야 하는데, 추의 최대 무게가 500g로 제한되어 있기 때문이다.

 

결국 추의 최대 무게는 500g이고, 30개이므로 시간 복잡도는 15000*2*n이 되는 것이다.

 

그러므로 충분히 문제를 해결할 수 있게 된다.

 

이 문제에서 핵심은 중복되는 경우를 제외하는 것이다.

 

중복되는 경우를 제거하지 않으면, 결국 시간복잡도는 앞서 계산한 O(3^n)이 되기 때문이다.

 

중복을 제거하는 방법은 많겠지만, 두 방법을 소개하면

 

1.

set을 만들어 만들 수 있는 수들 중 중복된 수를 제거한다.

i번째 무게추를 이용해 만들 수 있는 무게를 계산할 때, set에 있는 수들에 i번째 무게추를 더하는 경우, 빼는 경우를 추가한다.

 

2.

먼저 크기 15000의 배열을 만들어 만들 수 있는 수인지 체크를 한다.

배열을 순회하면서 만들 수 있는 수라면, 그 수에서 추를 뺀 경우와 추를 더한 경우도 만들 수 있는 수로 바꿔주면 된다.

 

+ 만약 [만들 수 있는 수 - 무게 추]가 음수가 된다면, 절대값을 씌워주면 계산하기 편하다.

(예를 들어 -6의 무게를 만들 수 있다는 것은 반대로 6의 무게를 반대편에 올린다는 뜻이기 때문이다.)

 

나는 이 중 set을 이용해 문제를 풀었다.

 

마지막으로 원하는 구슬의 무게를 만들 수 있는지 검사해 출력하면 된다.

 

 

​

[아이디어 정리]

1. 추의 최대 무게에 제한이 있으므로, 충분히 시간 복잡도 안에서 문제를 해결 할 수 있다.
2. 중복되는 경우를 제외해 시간 효율을 높인다.
3. 만들 수 있는 무게가 있다면, 그 무게에서 추의 무게를 더하는 경우와 빼는 경우를 추가한다. (추를 사용하지 않는 경우는 +0 이므로 계산하지 않아도 된다.)
4. 구슬의 무게가 만들 수 있는 무게인지 확인해 출력한다.

 

 

 

Code

 

 

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int main()
{
	int N,M;
	cin >> N;
	int a;
	set<int> nowS;
	nowS.insert(0);
	set<int> newS = nowS;
	for (int i = 0; i < N; i++) {
		cin >> a;
		for (set<int>::iterator it = nowS.begin(); it != nowS.end(); it++)
		{
			newS.insert(abs(*it + a)), newS.insert(abs(*it - a));
		}
		nowS = newS;
	}
	cin >> M;
	for (int i = 0; i < M; i++) 
	{
		cin >> a;
		if (nowS.find(a) != nowS.end())
			cout << "Y ";
		else
			cout << "N ";
	}

	return 0;
}

 

---

문제를 풀기전에 이게 시간안에 풀리나? 고민을 많이 했다

고민 끝에 일단 풀어보자고 생각하고 문제를 풀었더니 바로 풀렸다

왜 풀렸는지 고민을 하던 도중에 제한사항이 있어서 최악의 경우가 제한된다는 사실을 알았다.

해결방법을 고민하는 것도 좋지만 일단 풀어보는 것도 중요한 것 같다....

 

 

2629번: 양팔저울