백준 Gold 3 양팔저울

양팔저울 (백준 Gold 3)

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

n개의 추의 정보가 주어지고
m개의 ‘표현’ 가능 여부를 묻는 구슬의 무게가 주어진다

구슬 1개를 ‘양팔저울’에 올리고
이후 n개의 추를 적절히 활용하여 ‘균형’을 맞출 수 있는지를 묻는 문제

• 양팔 저울이 ‘수평’이어야 해당 구슬을 ‘표현 가능’함으로 여김
  

풀이 방법

dp의 문제이며
2차원 dp를 요구하는 문제이다

• dp[i][w] (bool) : i번째의 추까지를 ‘사용’하여 w란 값을 ‘표현 가능’한지를 확인
  그렇기에 ‘구슬’의 존재는 신경쓰지 않고
  각각의 ‘추’들을 이용하여 ‘어떤 무게’를 만들 수 있는지를 체크하기만 하면 됨
  

• 또한, i번째 추를 활용하는 방법은 다음과 같다
  

  • ‘올리지 않음’ : 이것 역시 하나의 선택지
    
  • ‘무거운 쪽’에 올림 : 차이를 극대화 하는 방법
    
  • ‘가벼운 쪽’에 올림 : 차이를 좁히거나 그 차이가 ‘뒤집어짐’
    

제출 코드

#include<iostream>
#include<vector>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<long> bids(n);
	long fullW = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> bids[i];
		fullW += bids[i];
	}

	long t;
	cin >> t;
	vector<long> checks(t);

	for (int i = 0; i < t; i++)
	{
		cin >> checks[i];
	}

	// dp[i][w] : i번째의 추까지 사용하여 w 값을 표현 가능한가? (양 저울의 차가 w인가?)
	vector<vector<bool>> dp(n + 1, vector<bool>(fullW + 1, false));

	dp[0][0] = true;

	for (int i = 1; i <= n; i++)
	{
		long nowBid = bids[i - 1];

		for (int j = 0; j <= fullW; j++)
		{
			if (dp[i - 1][j] == false)
				continue;

			// 추를 안올리는 경우
			dp[i][j] = true;

			// 추를 무거운 쪽에 올리는 경우
			if (j + nowBid <= fullW)
				dp[i][j + nowBid] = true;

			// 추를 가벼운 쪽에 올리는 경우
			if (abs(j - nowBid) <= fullW)
				dp[i][abs(j - nowBid)] = true;

		}
	}

	for (int i : checks)
	{
		if (i > fullW)
		{
			cout << "N ";
			continue;
		}

		if (dp[n][i])
		{
			cout << "Y ";
		}
		else
		{
			cout << "N ";
		}
	}

	return 0;
}

결과

2번 틀린 것은
마지막 체크 부분에서

if(i > fullW)

부분을 빼먹어서 그렇다
솔직히, 범위를 넘어선 접근이라 생각하였기에
‘런타임 에러’가 나올 것이라 생각했지만

곰곰히 생각해보니
‘반드시 런타임 에러’를 내뱉지 않을수도 있는 가능성이 있었다

그렇기에 범위를 넘어설 가능성을 제거하여 통과하였다

여담

사실 2~3번 정도 풀이법 접근에 시도하다 실패하여 결국 힌트를 받아 풀었다

1. 1차원 dp로 접근해보려다 실패함
   
   • 결국 ‘추’의 사용 여부를 ‘파악’해야 함
     
2. 2차원 dp로 접근하다 실패
   
   • dp[i][w] : i개를 사용하여 만들 수 있는 w 무게 확인
     
   • 거의 비슷한 개념이지만, 결국 사용한 추를 ‘확인’할
     방법을 찾지 못해 dp의 기준을 수정해야 했음
     
3. 추를 적용하는 방법에 대한 접근 실패
   
   • 정확히는 ‘가벼운 쪽’에 올리는 것을 단순히 ‘빼기’로 생각하여 실패
     
   • 가벼운 쪽에 올리면 ‘차이’가 좁혀지는 동시에, ‘뒤집어질’ 가능성을 염두하 두었어야 했음
     

dp를 잘 풀어보려면
다음과 같은 것을 항상 파악해야 함

1. 상태 찾기 - dp[i], dp[i][j]가 ‘무엇’을 의미해야 할까?
   
2. 점화식의 ‘이전 상태’ 고려하기 - 현재 상황은 이전 상황에서 어떤 상태가 되었는가
   
3. 중복 계산을 줄이려면 어떤 방향으로 순회해야 하는가 - i가 증가? 감소?
   

dp 는 많이 풀어봐야 하지만
다음과 같은 내용을 염두해보면서 풀면 더 효율적!