[백준] JAVA - 2629. 양팔저울

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

2629번: 양팔저울

생각

시간초과로 친구의 도움을 받아 문제를 해결했습니다ㅠㅠ

완전탐색을 해버리면 부분집합인 O(2^N)의 시간복잡도를 가지게 되고 구슬의 개수가 M개이니 총 O(M*2^N) 을 가지게 됩니다. 따라서 dp와 메모이제이션을 통해 문제를 풀어야 합니다.

 

양팔 저울에서 왼쪽에 구슬을 위치시키고 오른쪽에 추를 위치시켜서 무게를 찾는다고 생각합니다.

다음으로 dp[i][j] : i번까지 추를 확인했을때 무게 j를 만들 수 있다면 true 라고 점화식을 세웠습니다. ( i <= 30, j <= 30*500)

 

이 점화식을 범위 안에서 모두 채우는 재귀함수 solve(i,w) 는 아래와 같이 총 세가지 경우가 있습니다.

1. 왼쪽에 추를 추가하는 경우 -> solve(i+1, w+weight[i]) 

2. 오른쪽에 추를 추가하는 경우 -> solve(i+1, Math.abs(w-weight[i])) 

3. 추를 선택하지 않는 경우 -> solve(i+1, w) 

 

답을 출력해줄때는 구슬의 무게가 최대 무게(500g*30)보다 더 많이나갈수 있기 때문에 반드시 걸러줘야합니다ㅠㅠ

Java Code

package com.java.algorithm;

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

public class BOJ_2629_양팔저울 {
	static int N,M;
	static int[] weight; // 추
	static int[] beads; // 구슬
	static boolean[][] dp; // dp[i][j] : i번까지 추를 확인했을때 무게 j 를 만들수있다면 true
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		N = Integer.parseInt(br.readLine());
		weight = new int[31];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			weight[i] = Integer.parseInt(st.nextToken());
		}
		
		M = Integer.parseInt(br.readLine());
		beads = new int[M];
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < M; i++) {
			beads[i] = Integer.parseInt(st.nextToken());
		}
		dp = new boolean[31][15001];
		
		solve(0, 0);
		for (int i = 0; i < M; i++) {
			if(beads[i] > 15000) { // 만들수있는 최고무게보다 더 많이 나가면 못만드는 경우
				sb.append("N").append(" ");
			}
			else if(dp[N][beads[i]] == true) {
				sb.append("Y").append(" ");
			}else {
				sb.append("N").append(" ");
			}
		}
		System.out.print(sb);
	}
	
	private static void solve(int i, int w) {
		if(i > N) return;
		//i번까지 추를 확인해서 w 무게를 만들었으면 바로 리턴
		if(dp[i][w] == true) return;
		dp[i][w] = true;
		
		solve(i+1, w + weight[i]); // 추만있는쪽에 추 올리기
		solve(i+1, Math.abs(w-weight[i])); // 구슬쪽에 추 올리기
		solve(i+1, w); // 아무것도 안 올리기
	}

}