[백준 2629번] 양팔저울

문제 링크: 2629번 양팔저울

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

 

분류를 보면 꽤나 풀만한 문제이겠지만 시험 중에 만난다면 당황할 법하다. DP, 특히 배낭류 문제는 정말로 잘 보이지 않는다.

 

처음에는 집합을 쓸까 생각을 했다. 사실 가능한 무게를 담고있는 집합을 선언하고, 추를 하나씩 추가해나가면서 가능한 무게들을 집합에 추가해나가는 것이다. 그 구현체로 HashSet을 이용하면 특정 무게가 만들 수 있는 무게인지 확인하는 과정이 O(1)에 가능하기 때문에 가능한 풀이이며 근본적으로 냅색 알고리즘과 유사한 풀이로 보인다. 다만 문제를 풀 당시에는 집합을 새로 만들 생각을 하지 못하고 기존의 집합에 새로운 원소를 추가하려다보니 구현이 꼬여서 포기했다.

 

기본적인 아이디어는 다음과 같다. 무게가 k인 i번째 추까지 고려했을 때 무게 w가 가능한지의 여부, 즉 f(i, w)는, 다음을 고려하여 파악할 수 있다.

 

1. 지금 추를 포함하지 않는 경우

i-1번째 추까지 고려했을 때, w를 측정 가능한지 확인한다.

 

2. 이전에 측정한 무게에 지금 추를 추가로 놓는 경우

i-1번째 추까지 고려했을 때, w - k 또는 k - w를 측정 가능한지 확인한다.

 

3. 이전에 측정한 무게에 지금 추를 반대편에 놓는 경우

i-1번째 추까지 고려했을 때, w + k를 측정 가능한지 확인한다.

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int nw = Integer.parseInt(br.readLine());
        int[] w = new int[nw + 1];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= nw; i++) {
            w[i] = Integer.parseInt(st.nextToken());
        }

        boolean[][] dp = new boolean[40001][nw + 1];
        dp[0][0] = true;
        for (int c = 1; c <= nw; c++) {
            int cw = w[c];
            for (int r = 0; r <= 40000; r++) {
                if (r - cw >= 0 && dp[r - cw][c - 1]
                || cw - r >= 0 && dp[cw - r][c - 1]
                || dp[r][c - 1]
                || r + cw <= 40000 && dp[r + cw][c - 1]) {
                    dp[r][c] = true;
                }
            }
        }

        int inputs = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        while (inputs-- > 0) {
            int input = Integer.parseInt(st.nextToken());
            sb.append(dp[input][nw] ? 'Y' : 'N').append(' ');
        }
        System.out.print(sb);
    }
}