[BJ] 2629. 양팔저울

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

2629번: 양팔저울

 

예전에 dfs로 완전탐색 했을 때는 시간초과가 났던 문제인데 dp를 공부한 후 다시 푸니까 풀려서 기분이 좋다^^

 

 

✔ 문제 조건

1. 30개 이하의, N개의 추가 있으며, 각 추들의 무게는 500이하이다. 같은 무게의 추가 여러 개 있을 수 있다. 추의 무게를 담은 배열을 balls[N+1] 라고 한다면,
   N<=30, balls[i] <= 500
2. 무게를 확인할 구슬의 개수 M은 7이하이며, 확인할 구슬의 무게는 40, 000보다 작거나 같은 자연수다. 확인할 구슬의 무게들을 담을 배열을 target[M]이라고 한다면, M<=7, target[i] <= 40, 000

✔ 접근 과정

1. 무게가 1g인 추 하나만 있다면 1g만 확인 가능하다.
2. 무게가 각각 1g인 추 뿐만 아니라 4g인 추도 있다면
   1. 각각의 무게인 1g과 4g은 확인 가능하다.
   2. 두 추의 무게의 차인 3g도 확인 가능하다.
   3. 두 추의 무게의 합인 5g도 확인 가능하다.
3. 즉, i+1번째 추가 있다면
   1. i+1번째 추의 무게 balls[i+1]g은 확인 가능하다.
   2. 그 이전까지 확인 가능했던 무게 balls[i]g 도 확인 가능할 것이다. (i+1번째 추를 사용하지 않는 경우랑 같다.)
   3. 두 무게의 차인 abs(balls[i+1] - balls[i])g과 합인 abs(balls[i+1] + balls[i])g도 확인 가능하다.
4. 따라서 boolean형 배열 dp[i][k]이. i번째 추까지 살펴보았을 때 kg을 확인 가능한 경우라고 두었을 때
   1. dp[i-1][k]가 true라면 -> dp[i][k], dp[i][i번째 추와 i-1추의 무게 차이], dp[i][i번째 추와 i-1추의 무게 합]들은 모두 true가 된다.
   2. 이렇게 해서 마지막 N번째 추까지 살펴보았을 때 dp[N][k]가 true라면 kg은 확인 가능한 무게이다.
   3. 추는 최대 30개가 있으며, 확인할 구슬의 무게는 최대 40,000이다. 따라서 dp배열은 최대 dp[30][40,000]까지 선언될 수 잇다. 이때, 4 * 30 * 40, 000 = 48 * 10^5byte 까지의 메모리 공간을 필요로 하며 최대 메모리 제한은 128MB (128 * 10^6)이므로 메모리 초과가 나지 않는다.

 

import java.io.*;
import java.util.*;
// 210625

public class Main_BJ_2629_양팔저울 {
    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("src/res/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = stoi(br.readLine()); // 구슬 개수
        int[] balls = new int[N+1];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=1; i<=N; i++) {
            balls[i] = stoi(st.nextToken());
        }

        boolean[][] dp = new boolean[N+1][40001]; // 구슬 최대 무게 40,000
        dp[1][balls[1]] = true;

        for(int i=2; i<=N; i++) {
            int w = balls[i]; // i번째 구슬까지 따졌을 때
            dp[i][w] = true;
            for(int k=1; k<=40000; k++) {
                if(dp[i-1][k]) { // i-1번 구슬까지 따졌을 때 알 수 있는 무게라면
                    dp[i][k] = true;
                    int diff = Math.abs(w-k);
                    dp[i][diff] = true;
                    int plus = w+k;
                    if(plus>40000) continue;
                    dp[i][plus] = true;
                }
            }
        }

        int M = stoi(br.readLine()); // 무게 개수
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<M; i++) {
            int target = stoi(st.nextToken());
            if(dp[N][target]) System.out.print("Y");
            else System.out.print("N");
            if(i!=(M-1)) System.out.print(" ");
        }

        br.close();
    }

    static int stoi(String str) {
        return Integer.parseInt(str);
    }
}

 

참고> dfs로 완전탐색하고 시간 초과가 났던 코드다.

코드를 보아하니,

1) 왼쪽에 추를 올릴 수 있는 모든 경우의 수를 구하면서

2) 왼쪽에 올리고 남은 추들을 오른쪽에 올릴 수 있는 모든 경우의 수들도 구해서

3) 왼쪽 추들의 무게와 오른쪽 추들의 무게의 합들의 차이만큼 측정 가능하다고 표시했다.

다시보니 정말 열심히 짜긴 했다..ㅋㅋ

https://github.com/jhk828/Algorithm/blob/master/BJ/Main_BJ_2629_%EC%96%91%ED%8C%94%EC%A0%80%EC%9A%B8_fail.java