백준 2629 (양팔저울) - java

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

2629번: 양팔저울

문제

양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다.

무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다.

구슬이 3g인 경우 아래 <그림 1>과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다.

추들의 무게와 확인할 구슬들의 무게가 입력되었을 때, 주어진 추만을 사용하여 구슬의 무게를 확인 할 수 있는지를 결정하는 프로그램을 작성하시오.

 

유형 : DP (배낭 문제)

 

접근 방식

• 추를 하나씩 추가했을 때 측정할 수 있는 무게를 계속해서 갱신해나가는 배낭 문제 유형의 다이나믹 프로그래밍 문제이다.
• 해당 문제에서 주의해야 할 점은 1가지가 있다.
  • 보통 배낭 문제에서는 더하는 연산만 존재한다. 하지만 위 문제는 추를 왼쪽이나 오른쪽에 추가함으로서 즉 더하기와 동시에 빼기의 연산 또한 존재한다.

전체 코드

package DP;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// BOJ_2629_양팔저울 G3
// 2024_02_09
// time : 148 ms
// memory : 15984 KB

public class BOJ_2629_양팔저울 {
    static int n = 0;
    static int m = 0;
    static int[] choo; // 추의 무게 저장
    static int[] go; // 구슬의 무게 저장

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

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

        st = new StringTokenizer(br.readLine()," ");
        m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine()," ");
        go = new int[m];
        for(int i= 0 ; i< m ; i++){
            go[i] = Integer.parseInt(st.nextToken());
        }

        // dp[i][j] : i번째 추를 추가해서 j의 무게를 측정할 수 있는가 ?
        boolean[][] dp = new boolean[n+1][40001];

        dp[0][0] = true; // 무게 0은 잴수있다.
        dp[0][choo[0]] = true; // 첫번째 추의 무게를 잴 수 있다.

        for(int i = 1; i < n; i ++){

            for(int j=0; j <= 40000; j ++){

                dp[i][j] = dp[i-1][j] || dp[i][j]; // 이전의 값 가져오기

                // 추를 왼쪽이나 오른쪽에 다는것은 + , - 연산을 의미한다.
                if (dp[i-1][j]){

                    if(j + choo[i] <= 40000){
                        dp[i][j + choo[i]] = true;
                    }

                    dp[i][Math.abs(j - choo[i])] = true;
                }
            }
        }

        // 판단
        for(int i= 0 ; i < m ; i++){
            if(dp[n-1][go[i]])
                sb.append("Y ");

            else
                sb.append("N ");
        }
        System.out.println(sb);

        br.close();
    }
}