[백준 2629] 양팔저울 / 자바 / dp

#문제

레벨: G3
알고리즘: dp
풀이시간: 1:20
힌트 참조 유무: 유

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

---

#문제 풀이

**첫 번째 접근: 실패

처음 보자마자 **브루트 포스로 시간 복잡도가 통과되는지 확인했습니다. 구슬의 조합으로 해당 숫자를 잴 수 있는지 확인하려면, 숫자들의 플러스 마이너스의 조합입니다. 예를 들어 설명하겠습니다.

아래 4개의 숫자 사이에 + 혹은 - 를 대입하고 합을 구하면 측정할 수 있는 무게가 됩니다. 만약 모두 -로 값이 음수라면 절대값을 씌우면 됩니다. 모두가 +인 값과 동일하기 때문입니다. 이 방식의 최악의 시간복잡도를 따져보면, 빈칸의 들어갈 조합의 경우의 수이기 때문에 2^30(N 최대값) 입니다. 1,024 x 1,024 x 1,024 = 1,000,000,000 = 약 10억으로 시간복잡도 초과인 계산 수입니다.

두 번째 접근: 성공

규칙을 찾으려고 하여도 규칙을 찾을 수가 없었습니다. 자, 그럼 dp 도입을 생각해보겠습니다. 한 번 탐색한 상태는 더는 탐색하지 않는 것이므로 상태를 먼저 정의해야 합니다. 상태는 지금까지 탐색한 추들로 만들 수 있는 무게입니다. 그림을 통해 설명하겠습니다.

위처럼 dp를 통해 많은 dfs 루트들이 조기에 탐색 차단을 할 수 있습니다. dp의 시간복잡도는 공간복잡도와 같기 때문에
추의 개수 x 확인하고자 하는 구슬의 무게 입니다. 숫자를 대입해보면 30 x 40,000 =. 1,200,000이기 때문에 충분히 통과 가능합니다.

---

#풀이 코드

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

public class Main {
   static boolean[][] dp; // dp[i][j]: 추의 무게가 i일 때 j무게를 측정할 수 있는지 여부
   static int N;
   static int[] choo;

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

       // 추의 개수
       N = Integer.parseInt(br.readLine());
       choo = new int[N];

       // 추의 무게 입력
       StringTokenizer st = new StringTokenizer(br.readLine());
       int sum = 0;
       for(int i=0; i<N; i++) {
           choo[i] = Integer.parseInt(st.nextToken());
           sum += choo[i];
       }

       dp = new boolean[N+1][40001];
       dfs(0, 0);

       // 확인할 구슬의 개수
       int M = Integer.parseInt(br.readLine());
       StringBuilder sb = new StringBuilder();

       // 각 구슬에 대해 측정 가능 여부 확인
       st = new StringTokenizer(br.readLine());
       for(int i=0; i<M; i++) {
           int marble = Integer.parseInt(st.nextToken());
           boolean possible = false;
           for(int j=0; j<=N; j++) {
               if(dp[j][marble]) {
                   possible = true;
                   break;
               }
           }
           if(possible) sb.append("Y ");
           else sb.append("N ");
       }

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

   static void dfs(int idx, int weight) {
       // 이미 확인한 경우 종료
       if(dp[idx][weight]) return;

       dp[idx][weight] = true;
       if(idx == N) return;

       // 추를 사용하지 않는 경우
       dfs(idx+1, weight);
       // 추를 왼쪽에 놓는 경우
       dfs(idx+1, weight + choo[idx]);
       // 추를 오른쪽에 놓는 경우 (절대값 사용)
       dfs(idx+1, Math.abs(weight - choo[idx]));
   }
}