[knapsack][백준2629 Gold3] 양팔저울 Java

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

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

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

 

<그림 1> 구슬이 3g인지 확인하는 방법 1은 1g인 추, 4는 4g인 추, ●은 무게를 확인할 구슬)

 

<그림 2>와 같은 방법을 사용하면 구슬이 5g인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다.

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

 

 

입력

첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무게는 500g이하이며, 입력되는 무게들 사이에는 빈칸이 하나씩 있다. 세 번째 줄에는 무게를 확인하고자 하는 구슬들의 개수가 주어진다. 확인할 구슬의 개수는 7이하이다. 네 번째 줄에는 확인하고자 하는 구슬들의 무게가 자연수로 주어지며, 입력되는 무게들 사이에는 빈 칸이 하나씩 있다. 확인하고자 하는 구슬의 무게는 40,000보다 작거나 같은 자연수이다.

출력

주어진 각 구슬의 무게에 대하여 확인이 가능하면 Y, 아니면 N 을 차례로 출력한다. 출력은 한 개의 줄로 이루어지며, 각 구슬에 대한 답 사이에는 빈칸을 하나씩 둔다.

 

 

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

---

 

 

양팔저울에서 주어지는 추를 이용해서 구슬의 무게를 알아낼 수 있는지 판단하는 문제 

추는 사용안하거나 사용할 수 있다. 사용한다면 추의 위치는 구슬과 함께두거나, 따로 둘 수 있다.

 

문제 접근

1. 한쪽에 구슬만 두는 경우 

• 추를 사용해서 특정 무게를 만들 수 있을지 없을지 판단하면 된다. 
• 여기서 특정 무게는 구슬의 무게가 된다. 
• DP[추i][무게] = 추i까지 고려하였을 때 '무게'를 만들 수 있는 경우 ( 나는 경우의 수로 했지만 boolean으로 설정하는게 맞는것 같다.)
• DP[구슬 무게] > 0 이라면, 추로 구슬 무게 판단이 가능하다. 

2. 구슬과 추를 함께 두는 경우

• 양팔저울이 구슬의 무게를 판단 가능한 경우 이 때의 무게를 x라 하자. 
• 그럼 추로 x 무게를 만들 수 있는 경우와 추로 (x - 구슬) 무게를 만들 수 있는 경우가 존재한다는 것을 의미한다.
  • (dp[x] > 0) && (x - 구슬무게 >= 0) && (dp[x - 구슬무게] > 0)
• 단 무게 x는 알 수 없으니 모든 가능한 무게에 대해 하나씩 검사해야 하면 된다.

3. 추가 정리로

• 특정 추가 dp[x]와 dp[x - 구슬무게] 에 동시에 사용될 수 있지않을까? 그럴 수 있다.
• 하지만 그러면 해당 추를 양쪽에서 뺀 경우를 생각하면 걱정하지 않아도 되는 문제가 된다. 
• 예를들면, (구슬 무게 + 추1 + 추2 + 추3) = (추3 + 추4 + 추5) 이라면 당연히 추3를 뺴면 된다. 
• 즉, (구슬 무게 + 추1 + 추2) 무게에서 이미 true로 통과된다.

 

코드

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

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

        int gCount = Integer.parseInt(br.readLine());
        int[] gs = new int[gCount + 1];
        int[][] dp = new int[gCount + 1][45001];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= gCount; i++) {
            gs[i] = Integer.parseInt(st.nextToken());   // 추 1 ~ 500, 중복 가능
            dp[i][gs[i]] = 1;   // 추 하나로 만들 수 있는 경우 1 초기화
        }

        int ballCount = Integer.parseInt(br.readLine());
        int[] balls = new int[ballCount + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= ballCount; i++) {
            balls[i] = Integer.parseInt(st.nextToken()); // 구슬 1 ~ 40000
        }

        for (int i = 1; i <= gCount; i++) {
            for (int m = 1; m < 45001; m++) {
                dp[i][m] += dp[i - 1][m];   // 선택안하는 경우, 이전 경우의 수? 더하기.

                if(m - gs[i] >= 0){         // 추 선택하는 경우
                    dp[i][m] += dp[i - 1][m - gs[i]];
                }
//                System.out.print(dp[i][m] + " ");
            }
//            System.out.println();
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= ballCount; i++) {
            boolean balanced = false;

            // 추, 구슬 같이 두는 경우
            for (int m = 1; m < 45001; m++) {
                if (dp[gCount][m] > 0 && m - balls[i] >= 0 && dp[gCount][m - balls[i]] > 0) {
                    balanced = true;
                    break;
                }
            }

            // 구슬만 한쪽에 두는 경우
            if(dp[gCount][balls[i]] > 0) balanced = true;



            if (balanced) {
                sb.append("Y ") ;
            } else {
                sb.append("N ");
            }
        }

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