백준 2629 - 양팔저울

Java

2629 번 - 양팔저울

문제

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

접근 방법

문제에서 요구하는 것은 추를 양팔저울에 놔두어 해당하는 무게를 도출해낼 수 있는가를 묻고있다.
따라서, 구슬의 무게를 신경쓰지 말고 추들을 가지고 만들 수 있는 모든 무게들을 기록하여, 각 구슬이 기록한 무게 중에 있으면 true, 없으면 false를 반환한다.

추는 총 30개이며, 하나당 최대 500g이므로 추의 개수와 최대 무게인 30 * 500으로 2차원 배열 int[n+1][30 * 500 + 1] dp을 만든다.
이 dp는 i개의 추를 가지고 만들 수 있는 무게를 뜻한다.

이제 양팔 저울에 추를 하나 씩 올려보는데,

1. 추를 올리지 않는 경우
2. 무거운 쪽에 추를 올리는 경우
3. 가벼운 쪽에 추를 올리는 경우

로 나누어 진다.

1, 2, 3번을 각각 재귀함수로 실행하면 무게가 도출 되는데, 그 무게와 현재까지 쓴 추의 개수를 dp배열의 index로 접근하여 true로 만들어 준다.

이후 구슬의 무게가 주어질 때, 해당 dp의 무게 인덱스에 넣어 true이면 양팔 저울로 만들 수 있는 무게이므로 Y를 출력한다.

여기서 추가로 시간 단축을 하는데, 한번 만들어진 무게면 다시 탐색 할 필요가 없으니, 재귀함수의 시작에 조건문을 통해 해당 무게가 true이면 해당 메서드를 종료하도록 하여 시간초과를 방지한다.

코드

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

public class Main {
	static int[] arr;
	static int n;
	static boolean[][] dp;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		arr = new int[n];
		
		for(int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		
		dp = new boolean[n + 1][30 * 500 + 1];
		// 각 구슬을 왼쪽 저울에 올렸을 때 무게 확인 유무를 도출한다.
		recur(0,0);
		
		int m = sc.nextInt();
		for(int idx = 0; idx < m; idx++) {
			int curN = sc.nextInt();	// 현재 구슬
			
			//500g 추 30개를 추가한 것보다 무거운 구슬이라면
			if(curN > 30 * 500)
				System.out.print("N ");
			else if(dp[n][curN])		// 각 구슬의 무게를 대입해본다
				System.out.print("Y ");
			else
				System.out.print("N ");
		}
		
		sc.close();
	}
	
	static void recur(int cnt, int weight) {
		
		// 마지막 추를 올렸을 때
		if(cnt == n) {
			dp[cnt][weight] = true;
			return;
		}
		// 이미 계산한 무게라면
		if(dp[cnt][weight])
			return;
		
		dp[cnt][weight] = true;
		
		// 양쪽 저울 모두에 추를 올리지 않을 경우
		recur(cnt + 1, weight);
		// 무거운 저울 쪽에 추를 올릴 경우
		recur(cnt + 1, weight + arr[cnt]);
		// 가벼운 저울 쪽에 추를 올릴 경우
		recur(cnt + 1, Math.abs(weight - arr[cnt]));
	}
}

총평

후기

추를 이용하여 모든 무게들을 만드는 것이 핵심인 문제였다.
추를 통하여 구슬을 맞춘다는 생각을 벗어나, 구슬을 추에게 맞춘다는 역발상이 중요했다고 생각한다.

개선할 점

없습니다.