[BOJ] 백준 2629번 양팔저울 (Java)

#2629 양팔저울

난이도 : 골드 2

유형 : DP / 배낭문제(조합최적화)

 

2629번: 양팔저울

▸ 문제

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

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

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

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

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

▸ 입력

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

 

▸ 출력

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

 

 

문제 풀이 

해당 문제는 주어진 추의 무게로 구슬의 무게를 확인할 수 있는지 여부를 판단하는 것이다. 해당 문제의 구슬은 쪼갤 수 없으므로 0-1 배낭문제(Knapsack Problem) 종류의 문제이다.

(* 참고 : 쪼갤 수 있다면 Fractional 배낭문제이다.)

 

추의 개수 2개, 추의 무게 1g, 4g일 때 ,구할 수 있는 구슬의 무게는 다음과 같다.

ex) 1g, 4g, 1+4 = 5g, |1-4| = 3g 총 4개의 무게가 나온다

 

점화식으로는 상위 문제를 조합해나가는 것이 익숙치않아 재귀호출탐색 + 메모이제이션으로 조합하는 방식을 택했다. 

 

이를 어떻게 구해야할까?

0-1 배낭문제보다는 간단하다. 배낭문제는 max가 정해지고 그 한도 내에 넣을 수 있는 최대의 value를 골라내는 DP문제라면 이 문제는 그냥 추들이 낼 수 있는 숫자를 모두 조합하여 저장해주면 된다.

• 0< 추 무게 < 500 * 30 = 15,000
• 0< 구슬 무게 <40,000

 

추의 개수가 n개일 때는 추의 무게를 각 f(0), f(1), ... , f(n-1)이라고 한다면 구할 수 있는 구슬의 무게는 다음과 같다.

1)  기본적으로 f(0)g, .... , f(n-1)g n개의 무게를 구할 수 있다.

 

→  그리고 여러 개의 추를 합침으로써 새로운 무게를 잴 수 있다.

        sum{ f(0) ~ f(n-1) 2개 조합 } ;

        sum{ f(0) ~ f(n-1) 3개 조합 } ;

                        ~

        sum{ f(0) ~ f(n-1) n-1개 조합 } ;

 

→  마지막으로 여러 개의 추를 뺌으로써 새로운 무게를 잴 수 있다. (반대쪽 저울에 추를 올리면 된다.)

        sub{ f(0) ~ f(n-1) 2개 조합 } ;

        sub{ f(0) ~ f(n-1) 3개 조합 } ;

                        ~

        sub{ f(0) ~ f(n-1) n-1개 조합 } ;

 

따라서 추의 무게 조합 방법은 총 3가지임을 알 수 있다.

1. 추 하나 그대로 무게
2. 현재 추의 무게에 새로운 추 더하기 (구슬  <-> 추+새로운 추) 
3. 현재 추의 무게에 반대편에 새로운 추 더해서 총 무게 빼기 (구슬+새로운 추 <-> 추)

 

이를 재귀호출탐색 방식으로 코딩하면 다음과 같다. 

static void dp(int cnt, int num) {
		if(result[cnt][num]) return;
		result[cnt][num] = true;

		if(cnt == n) return;

		dp(cnt+1, num+ w[cnt]);
		dp(cnt+1, num);
		dp(cnt+1, Math.abs(num- w[cnt]));

	}

 

풀이 코드 

// #2629 dp topdown 양팔저울 
import java.io.*;
import java.util.*;

public class TwoArmScales {

	static int n;
	static int[] w;
	static boolean[][] result;

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

		n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());


		w = new int[n];
		result = new boolean[n+1][40001];
		for(int i=0; i<n; i++) {
			int src = Integer.parseInt(st.nextToken());
			w[i] = src;
		}

		dp(0,0);

		for(int j=0; j<20; j++) {
			if(result[n][j]) {
				System.out.println(j);
				System.out.print(result[n][j]+" ");
			}
		}

		int c = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<c; i++) {
			int t = Integer.parseInt(st.nextToken());

			if(result[n][t]) {
				sb.append("Y ");
			}else {
				sb.append("N ");
			}
		}

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

	static void dp(int cnt, int num) {
		if(result[cnt][num]) return;
		result[cnt][num] = true;

		if(cnt == n	) return;

		dp(cnt+1, num+ w[cnt]);
		dp(cnt+1, num);
		dp(cnt+1, Math.abs(num- w[cnt]));

	}
}

 

---

 

+ 다른 분 참고한 점화식 코드 (링크)

//조합
for(int i=1;i<=N;i++) {
	ArrayList<Integer> temp = new ArrayList<Integer>();
	temp.add(ball[i]);
	for(int j=1;j<=15000;j++) {
		if(isAvail[j]) {
			if(ball[i]-j > 0) {
				temp.add(ball[i]-j);
			}
			if(ball[i]+j <= 15000) {
				temp.add(ball[i]+j);
			}
			if(j-ball[i] > 0) {
				temp.add(j-ball[i]);
			}
		}
	}
	for(int j=0;j<temp.size();j++) {
		isAvail[temp.get(j)] = true;
	}
}