[백준] 양팔저울 2629번 C++ 풀이

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

2629번: 양팔저울

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> chu;
vector<int> gu;
bool visit[40001][31];
int chuCnt, guCnt;

void solve(int i, int w)
{
	if (i == chuCnt||visit[w][i]==true) {
		visit[w][i] = true;
		return;
	}
	visit[w][i] = true;
	solve(i + 1, w + chu[i]);
	solve(i + 1, abs(w-chu[i]));
	solve(i + 1, w);
}

int main(void)
{
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	int weight;
	cin >> chuCnt;
	for (int i = 0; i < chuCnt; i++)
	{
		cin >> weight;
		chu.push_back(weight);
	}

	solve(0, 0);

	cin >> guCnt;
	for (int i = 0; i < guCnt; i++)
	{
		cin >> weight;
		if (visit[weight][chuCnt] == true)
			cout << "Y ";
		else
			cout << "N ";
	}

}

왼쪽 저울은 구슬이 놓여져있는 저울, 오른쪽 저울은 추를 놓을 저울이라고 생각한다.

추는 왼쪽 또는 오른쪽에 놓을수 있다.

왼쪽에 추를 놓는 경우에는 오른쪽 추의 무게 = 오른쪽 추의 무게 - 왼쪽 추의 무게 로 생각할 수 있다.

왼쪽에 추를 놓는 무게만큼 오른쪽 추의 무게가 가벼워 진다고 생각해도 좋다.( 그만큼 뺄것이니 )

오른쪽에 추를 놓는 경우는 그냥 원래 오른쪽 저울에 쌓인 무게에 추의 무게를 더해주면 된다.

추를 전혀 저울에 놓지 않을 수도 있다.

 

정리해서 추를 놓는 방법은 총 3가지이다.

1. 왼쪽 저울에 놓기 ( 오른쪽 저울의 무게에 왼쪽 저울에 놓을 추의 무게를 빼주면 된다. )

solve(i + 1, abs(w-chu[i]));

물론 절댓값으로 처리한 이유는 음수가 발생할 수도 있기 때문이며,

이 경우 왼쪽 저울의 무게와 오른쪽 저울의 무게를 서로 바꿔 오른쪽의 저울의 무게가 항상 왼쪽 저울의 무게보다 크게 만들기 위해서이다.

왼쪽 저울의 무게가 오른쪽 저울의 무게보다 크면 안되니깐~! 왜냐 구슬의 무게를 못구한다...

그러므로 그냥 왼쪽 저울과 오른쪽 저울의 무게를 바꿔 준다.

왼쪽저울의 무게를 오른쪽 저울에도 만들수 있고 오른쪽 저울의 무게를 왼쪽 저울에 만들어 줄 수 있으니..!

 

2. 오른쪽 저울에 놓기 ( 오른쪽 저울의 무게에 오른쪽 저울에 놓을 추의 무게를 더해준다. )

solve(i + 1, w + chu[i]);

3. 저울에 올리지 않기. ( 그냥 오른쪽 저울의 무게를 그대로 가져간다 )

solve(i + 1, w);

 

 

- 시간초과

if (i == chuCnt||visit[w][i]==true) {
		visit[w][i] = true;
		return;
}

시간 초과를 방지하기위해 i번째 추를 놓을때 이미 그 무게에 대한 경로(방법)을 이미 방문한 적이 있는경우

또 똑같은 탐색을 하면 시간이 걸리므로 이미 방문이 된곳은 그냥 return 해준다.

이 if문 아래에 visit[w][i]가 있지만 이것은 모든 추를 사용하기 전인 과정중에 방문 체크 용도이고

if문 안에 또 visit[w][i]를 한 이유는 배열이 아닌 vector를 내가 사용했기때문에 딱 개수에 맞춰 i번째까지 구한 경우

그 무게에 대해 방문 처리를 해줘야한다. 아니면 모든 추를 사용하여 만든 무게에 대한 visit를 저장하지 않는다..ㅠ