[Algorithm] 백준 2629 양팔저울

문제

2629번: 양팔저울

 

dp 의 냄새는 나지만 어떻게 풀어야될지 몰라서 틀린 문제입니다.

dp 는 익숙해지는게 어려운 주제인거 같지만 그래도 공부하면 할수록 보이는거 같습니다. 

 

이 문제의 핵심은 knapsack 0-1 입니다.

해당 개념을 모르신다면 백준 12865를 꼭 풀어보시고 풀이를 확인해보시길 바랍니다.

 

2023.07.04 - [Algorithm🧩] - 백준 12865 평범한 배낭 (0-1 knapsack)

 

 

💡풀이

knapsack 1-0 를 떠올려야하는 이유는 구슬을 쓸 수도 있고 안 쓸 수도 있기 때문입니다. 구슬을 차례대로 살펴보며 쓰는 경우와 안 쓰는 경우로 나눠보도록 하겠습니다. 

 

i번째 구슬을 확인하고 있을 때

(1) 현재 구슬을 단독으로 쓰는 경우 

• 현재 구슬의 무게는 확인 가능

(2) 이전 구슬만 쓰는 경우

• 현재 살펴보고 있는 구슬 i를 쓰지 않고 i-1 까지 살펴본 구슬들을 그대로 쓰는 경우

(3) 이전 구슬과 같이 쓴다 - 구슬을 쓰는 경우

• 현재 살펴보고 있는 구슬 i를 i-1 까지 살펴본 구슬들과 같이 쓰는 경우

말로는 애매해서 그림으로 보도록 하겠습니다. 

 

💡예시

 

구슬 무게가 각각 1, 2, 2, 3 입니다. 

 

dp[i][j] : i 번째 구슬을 살펴볼 때 무게 j를 만들 수 있으면 1 아니면 0

 

dp 초기화

0번째 구슬부터 살펴보면 무게 1 단독으로 만들 수 있는 무게는 본인 무게 1 밖에 없습니다.

 

테이블 초기화

 dp 테이블 채우기 - 점화식 세우기

1번째 구슬부터 점화식이 적용됩니다. 0번째 구슬 탐색을 기반으로 1번째에 대해 표를 채워나가도록 하겠습니다.  

 

 

(1) 현재 구슬을 단독으로 쓰는 경우 

• 현재 구슬의 무게는 확인 가능

dp[i][i번째 추의 무게] = 1

(2) 이전 구슬만 쓰는 경우

• 현재 살펴보고 있는 구슬 i를 쓰지 않고 i-1 까지 살펴본 구슬들을 그대로 쓰는 경우

dp[i-1][w] 가 1이면 dp[i][w] 또한 1

 

(3) 이전 구슬과 같이 쓴다 - 구슬을 쓰는 경우

• 현재 살펴보고 있는 구슬 i를 i-1 까지 살펴본 구슬들과 같이 쓰는 경우

1. 서로 같은 저울 방향에 올린다면 더하기

dp[i-1][w] 가 1이면 dp[i][w 와 현재의 추 무게 합] = 1 

 

예시에서는 dp[0][1] = 1 이기 때문에 dp[1][1 + 2] = 1

 

2. 서로 다른 저울 방향에 올린다면 빼기

 

dp[i-1][w] 가 1이면 dp[i][w 와 현재의 추 무게 차] = 1

 

예시에서는 dp[0][1] = 1 이기 때문에 dp[1][Math.abs(1 - 2)] = 1

 

 

계속 표를 채워나가보자

 

i = 2 일 때

 

i = 3 일 때

 

❗코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 10:34
        // 가벼운 순으로 주어짐. 같은 무게 여러개 가능
        // dp[i][j] : i번째 구슬을 올릴 때 무게 j를 만들 수 있는지 여부 - 1이면 가능
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int MAX_LIMIT = 40000;

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

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

        int[][] dp = new int[N][MAX_LIMIT+1];

        // 초기화
        dp[0][choo[0]] = 1;

        for(int i = 1; i < N; i++) {
            
            // 1
            int weight = choo[i];
            dp[i][weight] = 1;
            for(int j = 1; j < MAX_LIMIT + 1; j++) {
                if(dp[i-1][j] == 0) continue;

                // dp[i-1][j] == 1 이라면
                
                // 2
                dp[i][j] = 1;

                // 3
                int add = j + weight;
                int sub = Math.abs(j - weight);
                if(add < MAX_LIMIT+1) dp[i][add] = 1;
                dp[i][sub] = 1;
            }
        }

        for(int i = 0; i < M; i++) {
            int goal = goo[i];
            if(dp[N-1][goal] == 1) bw.write("Y");
            else bw.write("N");

            if(i != M-1) bw.write(" ");
        }

        bw.flush();
    }

}