Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

23. 동적 계획법2

조금 더 어려운 동적 계획법 문제를 풀어 봅시다.

Java / Python

5. 양팔저울

2629번

예전에 배웠던 냅색 알고리즘으로 푸는 문제

이번 문제는 양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하는 것으로, 추들의 무게와 확인할 구슬들의 무게가 입력되었을 때, 주어진 추만을 사용하여 구슬의 무게를 확인 할 수 있는지를 결정하는 프로그램을 작성하는 문제입니다.

• 입력
  
  첫째 줄 : 추의 개수(30 이하)
  
  둘째 줄 : 추의 무게들이 자연수로 가벼운 것부터 차례로
  (같은 무게의 추가 여러 개 가능, 추의 무게: 500g이하)
  
  세 번째 줄 : 무게를 확인하고자 하는 구슬들의 개수 (구슬의 개수는 7이하)
  
  네 번째 줄 : 확인하고자 하는 구슬들의 무게 (자연수, 구슬의 무게는 40,000보다 작거나 같은 자연수)
  
  
• 출력
  
  주어진 각 구슬의 무게에 대하여 확인이 가능하면 Y, 아니면 N 을 차례로 출력합니다.

• Java

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

public class Main {

	static int N;	// 추 개수
	static int[] sinkers;	// 추 무게들
	static boolean[][] dp;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
		N = Integer.parseInt(br.readLine());
		sinkers = new int[N];
		dp = new boolean[N + 1][55001]; 
		// 추의 최대 무게합(15000g) + 구슬 최대 무게 (40000) = 55000
        
		StringTokenizer st = new StringTokenizer(br.readLine());         
		for (int i = 0; i < N; i++) {  
			sinkers[i] = Integer.parseInt(st.nextToken());            
		}

		int M = Integer.parseInt(br.readLine());
		int[] beads = new int[M];
        
		st = new StringTokenizer(br.readLine());  
		for(int i = 0; i < M; i++){	 
			beads[i] = Integer.parseInt(st.nextToken());
		}
        
		dfs(0, 0);
        
		for(int i = 0; i < M; i++){
			if(dp[N][beads[i]]){
                bw.write("Y ");
			}else {
				bw.write("N ");
			}
		}

		bw.flush();
		bw.close();
		br.close();
	}
	public static void dfs(int cnt, int weight) {
		if(dp[cnt][weight]) return;
        
		dp[cnt][weight] = true;
        
		if(cnt == N) return;
        
		dfs(cnt + 1, weight + sinkers[cnt]);	// 추 무게 합
		dfs(cnt + 1, weight);					// 추 사용 안 하는 경우
		dfs(cnt + 1, Math.abs(weight - sinkers[cnt]));	// 구슬 있는 곳에 추 더하기

	}
}

• Python

import sys
N = int(sys.stdin.readline())
sinkers = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
beads = list(map(int, sys.stdin.readline().split()))
dp = [[0]*15001 for _ in range(N + 1)]
possible = []

def dfs(sinkers, n, now, left, right):
    new = abs(left - right)
        
    if new not in possible:
        possible.append(new)
        
    if now == n : return 0
        
    if dp[now][new] == 0:
        dfs(sinkers, n, now + 1, left + sinkers[now], right) # 저울 왼쪽
        dfs(sinkers, n, now + 1, left, right + sinkers[now]) # 저울 오른쪽
        dfs(sinkers, n, now + 1, left, right) # 저울에 안 놓음
        dp[now][new] = 1

dfs(sinkers, N, 0, 0, 0)
for i in range(0, M):
    if beads[i] in possible:
        print('Y', end=' ')
    else:
        print('N', end=' ')