[백준 2629번] 양팔저울 (C++)

문제링크 : https://www.acmicpc.net/problem/2629

2629번: 양팔저울

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, guseul, w;
int arr[31];
int dp[31][40001];

void func(int idx, int weight)
{
    if(idx>N || dp[idx][weight]) return;
    dp[idx][weight]=1;
    func(idx+1, weight+arr[idx]); //i번째 무게추를 구슬쪽 저울에 올림
    func(idx+1, abs(weight-arr[idx])); //i번째 무게추를 구슬 반대편 저울에 올림
    func(idx+1, weight); //i번째 무게추를 올리지 않음
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    for(int i=0; i<N; i++)
    {
        cin >> arr[i]; //추의 무게
    }
    cin >> guseul;
    func(0, 0);
    for(int i=0; i<guseul; i++)
    {
        cin >> w; //확인해야 하는 무게
        cout << (dp[N][w] ? "Y " : "N ");
    }

    return 0;
}

해당 문제의 경우 경우의 수가 아래와 같이 3가지가 있다.

1. 저울에 구슬과 같이 무게추를 올림
2. 구슬 반대편 저울에 무게추를 올림
3. 무게추를 올리지 않음

각 케이스에 대해 3가지 경우의 수를 검토해주고 또 나온 결과에 대해서 3가지 경우의 수를 검토해주는 것을 반복한다.

중복한 결과에 대해서 다시 탐색할 수 있으므로 현재 dp[idx][weight]가 1이라면 바로 종료시켜준다. (시간초과 방지)

그리고 idx과 weight를 넘겨주는데 idx가 N을 넘어서면 안되므로 해당 경우에도 종료시켜주도록 한다.

 

검토한 케이스에 대해서 우리가 확인해야 하는 dp[N][w]의 값이 1이라면 가능하다는 것이므로 Y를 출력하고 검토당시 불가능했다면 0이 담겨있으므로 N을 출력한다.

 

참고로 위 문제에서 dp 배열을 [31][40001]으로 선언해주었으나, 무게의 합이 최대 15000(30*500)이므로 15000까지만 선언하고 x가 15000이 넘을 때 바로 N이 되도록 해주면 메모리가 절약된다. (x의 입력자체는 40000만까지 가능)

 

해당 문제는 재귀말고도 반복문을 통해서 풀 수 있었으므로 다음 방식으로도 풀어보았다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, guseul, w, sum;
int arr[31];
int dp[31][40001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    for(int i=0; i<N; i++)
    {
        cin >> arr[i]; //추의 무게
        sum+=arr[i]; //무게 합 저장
    }
    dp[0][0] = dp[0][arr[0]] = 1; //구슬 할당을 하는가 안하는가
    for(int i=1; i<N; i++)
    {
        for(int j=0; j<=sum; j++)
        {
            if(!dp[i-1][j]) continue;
            dp[i][j+arr[i]] = 1; //i번째 무게추를 구슬쪽 저울에 올림
            dp[i][abs(j-arr[i])] = 1; //i번째 무게추를 구슬 반대편 저울에 올림
            dp[i][j]=1; //아무것도 하지 않음
        }
    }

    cin >> guseul;
    for(int i=0; i<guseul; i++)
    {
        cin >> w; //확인해야 하는 무게
        cout << (dp[N-1][w] ? "Y " : "N ");
    }

    return 0;
}

핵심 내용은 3가지 경우의 수를 탐색해주는 것으로 위와 동일하다.

여기서는 처음에 초기화를 2가지를 해주고 시작한다. 

구슬 할당 o : dp[0][arr[0]]
구슬 할당 x : dp[0][0]

구슬 할당을 했을 때와  안 했을 때 2가지로 나눠서 미리 초기화를 시켜주고 진행한다.

직전값이 1일 때 즉 저번값에 이어서 탐색이 가능할때 이어서 3가지 경우의 수에 대해 탐색을 해준다.