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

https://www.acmicpc.net/problem/17610

17610번: 양팔저울

풀이

틀렸습니다와 런타임 에러로 고생한 문제... 이문제 난이도가 실버 1이라니 ..ㅜ

어떻게 해야할까 생각하다가 알고리즘 분류에 브루트포스 알고리즘을 보자말자 '완전탐색 문제구나' 했다.

 

우선 위의 그림과 같이 양팔저울을 한 번만 사용하여 그릇에 담을 수 있는 무게를 구해야한다.

이 경우의 수는 아래의 이미지와 같다.

따라서, 양팔저울에 무게추를 올리는 경우의 수는 다음과 같이 정리할 수 있다.

• 현재 무게추를 올리지 않고, 입력받는 다음 무게추를 올리는 방법
• 현재 무게추를 반대편에 올리는 방법 (빈 그릇쪽)
• 현재 무게추를 오른쪽에 올리는 방법

 

이 부분을 유의하고, 완전탐색을 이용하여 문제를 풀면 된다.

요즘 알고리즘 문제를 푸는데, 완전탐색 (Brute Force), 백트래킹 (Back Tracking)쪽에서 자주 헤매는것 같다.

 

Code

#include <iostream>

using namespace std;

bool _isExist[10000000];
int _gi[14];
int k;
int sum;
int result;

void recursive(int idx, int input)
{
	if (input >= 1)
	{
		if (!_isExist[input])
			result++;
		_isExist[input] = true;
	}

	if (idx == k)
		return;

	recursive(idx + 1, input + _gi[idx]);
	recursive(idx + 1, input - _gi[idx]);
	recursive(idx + 1, input);
}

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

	cin >> k;

	for (int i = 0; i < k; i++)
	{
		cin >> _gi[i];

		sum += _gi[i];
	}

	recursive(0, 0);

	cout << sum - result << "\n";
}