백준 2629번: 양팔저울

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

참고한 블로그 : https://cocoon1787.tistory.com/360



무게추들을 이용해서 만들 수 있는 모든 무게를 구해서 주어진 구슬의 무게가 있으면 Y, 없으면 N을 출력하려고 했다. 근데 원래 풀던 문제들과 다르게 양팔 저울이어서 무게가 더해질수도, 빼질수도 있는 문제라서 점화식을 어떻게 세워야 할 지 생각하기가 어려웠다.

i번째 추가 사용될 수 있는 방법은 다음 3가지와 같다.
1. 저울에 올리지 않는다.
2. 구슬의 반대편에 올린다.
3. 구슬 쪽에 올린다.

따라서 위 3개를 재귀함수로 호출해서 dp 배열 값을 채워주면 끝나는 문제였다. 2차원 배열로 선언하고, dp[i][j]는 i번째 추를 사용했을 때 만들어지는 무게가 j라는 뜻으로, 값은 0과 1만 저장해서 True/False를 표현했다. 즉 dp[i][j] = 1이면 i번째 추를 이용해서 무게 j를 만들 수 있다는 뜻이다.

<작성한 코드>

#include <iostream>
#include <cmath>
using namespace std;
int weight[31], dp[31][15001];
int n, k;

void DP(int i, int w){
    if(n < i || dp[i][w])
        return ;
        
    dp[i][w] = 1;
    DP(i + 1, w); // i번째 추를 안올림
    DP(i + 1, w + weight[i]); // i번째 추를 구슬 반대편에 올렸을 때 무게
    DP(i + 1, abs(w - weight[i])); // i번째 추를 구슬 쪽에 올렸을 때 무게
}

int main(){
    cin >> n; // 추 개수
    for(int i = 0; i < n; i++)
        cin >> weight[i];
    
    DP(0, 0);
    
    cin >> k; // 구슬 개수
    for(int i = 0; i < k; i++){
        int bead;
        cin >> bead;
        if(bead > 15000) // 최대 무게 500g x * 최대 개수 30개
            cout << "N ";
        else if(dp[n][bead])
            cout << "Y ";
        else
            cout << "N ";
    }
}

DP()의 함수 종료 조건인 if문에서, 처음에는 i가 추의 개수 n보다 커질 경우만 종료하도록 했었는데 그렇게 제출했더니 시간 초과가 떴다. 블로그에서처럼 dp[i][w]가 참인지 거짓인지의 조건까지 넣어야 통과가 됐는데, 몇 번째 추까지 사용을 했든간에 그 값이 0(False)이면 어차피 만들 수 없는 무게이므로 재귀함수 호출을 더 하지 않고 끝을 내서 시간을 줄이는 것인가 싶다. 종료 조건이 제일 어렵다 정말.