문제

양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다.

무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다.

구슬이 3g인 경우 아래 <그림 1>과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다.

<그림 2>와 같은 방법을 사용하면 구슬이 5g인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다.

추들의 무게와 확인할 구슬들의 무게가 입력되었을 때, 주어진 추만을 사용하여 구슬의 무게를 확인 할 수 있는지를 결정하는 프로그램을 작성하시오.

문제풀이

사용한 알고리즘 : 구현

임의의 무게 W 를 만들 때 모든 추들은

1. 쓰이지 않는경우

2. + 로 쓰이는 경우

3. - 로 쓰이는 경우

3중 하나입니다.

문제의 예를 들어 1, 4 의 추가 있다고 하고 모든 가능한 무게를 생각해보면,

위와 같이 됩니다.

따라서 만들어지는 모든 숫자를 저장할 set을 하나 만듭니다.

set에는 0 을 넣어 놓고 시작합니다.

모든 추를 둘러 보면서 이전에 만들고 set에 저장해 놓은 무게들에 대해

1. 더해서 새로운 무게를 만든다.

2. 빼서 새로운 무게를 만든다.

를 실행합니다.

위의 예를 생각해보면, 아래와 같이 진행 되겠죠.

과정 (2)에서, 각 탐색 시 새로 만들어 지는 무게를 따로 저장해 놨다가 set에 추가해야 합니다.

바로 추가할 경우 set에 추가된 수로 또 만들고 또 만들고... 할꺼에요...

	#include <bits/stdc++.h>
	using namespace std;
	const int DMAX = 30;// 추 개수는 최대 30개

	int N, M;
	int arr[DMAX]; // 추
	set<int> S;

	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

	cin >> N;
	for (int i = 0; i < N; ++i) cin >> arr[i];

	S.insert(0);
	// i ~ 끝까지로 만들 수 있는거 ( 중복방지 )
	for (int i = 0; i < N; ++i) {
	vector<int> temp;
	for (auto it: S) {
	temp.push_back(it + arr[i]);
	temp.push_back(it - arr[i]);
	}
	for (auto t : temp) S.insert(t);
	}

	cin >> M;
	for (int i = 0; i < M; ++i) {
	int num;
	cin >> num;
	if (S.count(num)) cout << "Y" << '\n';
	else cout << "N" << '\n';
	}

	return 0;
	}

view raw BOJ 2629.cpp hosted with ❤ by GitHub