[백준 2629] 양팔저울

 

 

어려웠던 부분 및 풀이

배낭 알고리즘을 공부하면서 풀었던 문제이다. 그래서 배낭 알고리즘을 어떻게 적용해야 하는지 생각해야 했던 부분이 어려웠다.

이 문제는 현재 추를 고려했을 때 만들 수 있는 무게의 차이를 구하는 dp문제이다.

 

추를 고려할 때 생각할 수 있는 선택지는 아래와 같다.

1. 사용하지 않는 경우
2. 사용하는 경우
   1. 가벼운 쪽에 추를 올려놓은 경우
   2. 무거운 쪽에 추를 올려놓은 경우

예제로 설명해보면 아래와 같다.

추의 무게는 1kg, 4kg, 6kg, 7kg 이다.

현재 상태는 1kg이 왼쪽, 4kg이 오른쪽에 놓여있다. 현재 무게의 차이는 3kg이므로 3kg의 구슬의 무게를 확인할 수 있다.

 

다음에 고려할 추의 무게는 6kg이다.

1. 추를 사용하지 않는 경우에는 무게의 차이가 3kg으로 동일하다. 즉, dp[i][j] = dp[i-1][j]이다.
2. 추를 사용하는 경우에는 두가지의 경우가 있다.
   1. 가벼운 쪽에 추를 올려놓는 경우, 무게의 차이가 3kg이다. 
   2. 무거운 쪽에 추를 올려놓는 경우, 무게의 차이가 9kg이다.

가벼운 쪽에 추를 올려놓는 경우, '현재 무게의 차이 - 추의 무게'이다. 하지만, 여기서 왼쪽이 무거운지 오른쪽이 무거운지에 상관없이 무게의 '차이'를 구해주어야 하기 때문에 절댓값으로 구해주어야 한다. 즉, dp[i][j] = dp[i-1][abs(j-w)]가 된다.

 

무거운 쪽에 추를 올려놓는 경우, '현재 무게의 차이 + 추의 무게'이다. 즉, dp[i][j] = dp[i-1][j+w]이다.

 

또한, 범위 체크도 해주어야 한다. 추의 개수는 최대 30개이고, 최대 무게는 500g이다. 그러면 최대한 만들 수 있는 무게의 차이는 30 * 500g이므로 15000이다. 즉, dp[][]에서 열의 개수를 15001 개를 만들어 주면 된다. dp행은 추의 개수+1만큼 만들어주면 된다.

 

무거운 쪽에 추를 올려놓는 경우, '현재 무게의 차이 + 추의 무게'이므로 15000을 넘을 수 있기 때문에 합의 결과가 15000이 넘지 않는 경우에만 고려해주어야 한다.

 

 

구현

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

public class Solution_for_2629 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int weightCnt = Integer.parseInt(st.nextToken());
        int[] weights = new int[weightCnt+1];

        st = new StringTokenizer(br.readLine());
        for (int w = 1; w < weightCnt+1; w++) {
            weights[w] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        
        int beadCnt = Integer.parseInt(st.nextToken());
        int[] beads = new int[beadCnt+1];

        st = new StringTokenizer(br.readLine());
        for (int b = 1; b < beadCnt+1; b++) {
            beads[b] = Integer.parseInt(st.nextToken());
        }

        boolean[][] dp = new boolean[weightCnt + 1][15001];
        dp[0][0] = true;

        for (int i = 1; i < weightCnt + 1; i++) {
            // 현재 추의 무게
            int curWeight = weights[i];
            
            // 현재 추 1개만 사용하는 경우
            dp[i][curWeight] = true;

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

                // 현재 추를 사용하지 않는 경우
                dp[i][j] = true;

                // 현재 추를 무거운 쪽에 올린 경우
                if (j + curWeight < 15001)
                    dp[i][j + curWeight] = true;

                // 현재 추를 가벼운 쪽에 올린 경우
                int diff = Math.abs(j - curWeight);
                dp[i][diff] = true;
            }
        }

        for (int b = 1; b < beadCnt+1; b++)  {
            if (15000 < beads[b]) System.out.print("N" + " ");
            else System.out.print((dp[weightCnt][beads[b]] ? "Y" : "N") + " ");
        }
    }
}