[BOJ] 2629 양팔저울 - Java

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

2629번: 양팔저울

[풀이]

양팔 저울의 양쪽에 올릴 수 있는 모든 추의 조합을 구해서 O(N^4)로도 할 수 있겠지만 그건 당연히 시간 초과일 것..

끙끙대다가 풀이를 보았고 dp를 이용해서 푸는 문제라는 것을 알게 되었다.

dp = boolean[N+1][30001]; //n번째 추를 올려놓았을 때 만들 수 있는 추의 무게에 true를 표시한다.

-> 예를 들어 (왼쪽) 추+a+b = c+d+e+f (오른쪽) => 추 = c+d+e+f - (a+b)

 

추는 N개까지이고, 만들 수 있는 추의 무게의 범위는 30개 * 500g = 15000g 이다.

근데 왼쪽에 올린 추들의 무게의 합이 오른쪽보다 큰 경우가 있으므로 음수도 함께 고려하기 위해 30001로 dp를 선언한다. (-15000~15000)

** 여담) 다른 분들은 풀이에서 Math.abs()를 이용해서 절댓값으로 풀이하셨던데 나는 이해가 안간다.. 음수인 경우를 고려하지 않고 어떻게 모든 경우를 생각하는거지..? 아시는 분 있으면 댓글 달아주세요,,

 

추를 놓는 경우는 아래와 같이 세가지이다. -> dfs 진행해서 dp 채우기

- 구슬은 무조건 왼쪽에 놓는다고 가정

1. n번째 추를 오른쪽에 놓는 경우

2. n번째 추를 놓지 않는 경우

3. n번째 추를 왼쪽에 구슬과 함께 놓는 경우

 

[코드]

 

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

public class Main {
    static StringTokenizer st;
    static int N,K;
    static int[] weights;
    static boolean[][] isPossible;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception{
        //System.setIn(new FileInputStream("src/main/java/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        weights = new int[N];
        isPossible = new boolean[N+1][30001]; //추 무게의 최대 총합은 15000, -도 고려

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            weights[i] = Integer.parseInt(st.nextToken());
        }

        //같은 무게의 추가 여러 개 있을 수도 있음
        dfs(0,15000);

        K = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int k=0;k<K;k++){
            int num = Integer.parseInt(st.nextToken())+15000;
            //Y,N 출력하기
            if(num>15000+15000){
                sb.append("N ");
            }else{
                if(isPossible[N][num]){
                    sb.append("Y ");
                }
                else{
                    sb.append("N ");
                }
            }

        }
        System.out.println(sb.toString());
    }

    static void dfs(int count, int sum){
        if(isPossible[count][sum]){
            return;
        }
        isPossible[count][sum] = true;

        if(count>=N){
            return;
        }

        //오른쪽에 놓은 경우
        dfs(count+1,sum+weights[count]);
        //둘 다 안놓은 경우
        dfs(count+1,sum);
        //왼쪽에 놓은 경우(타깃과 같이)
        dfs(count+1,sum-weights[count]);
    }
}