양팔 저울 (정올 1352,백준 2629)

문제 링크

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=627&sca=99&sfl=wr_hit&stx=1352 

JUNGOL

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

2629번: 양팔저울

풀이

dp에 현재 가지고 있는 추로 잴수있는 모든 경우를 표시해 놓는다.

 

코드

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

public class Main {
	static boolean[][] dp;
	static int[] w;
	static int n;
	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());
		w=new int[n+1];
		dp=new boolean[31][15000];
		StringTokenizer st=new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			w[i]=Integer.parseInt(st.nextToken());
		}
		solv(0,0);
		int m=Integer.parseInt(br.readLine());
		st=new StringTokenizer(br.readLine());
		StringBuilder sb=new StringBuilder();
		for(int i=1;i<=m;i++) {
			int temp=Integer.parseInt(st.nextToken());
			if(temp>15000)sb.append("N ");//500g * 30개 
			else if(dp[n][temp])sb.append("Y ");
			else sb.append("N ");
		}
		//----------------입력
		bw.append(sb.toString());
		bw.flush();
		bw.close();
	}
	private static void solv(int idx, int now) {
		if(idx>n||dp[idx][now])return;
		dp[idx][now]=true;//방문
		solv(idx+1, now+w[idx]);//추를 올린 경우
		solv(idx+1, now);//추를 올리지 않은 경우
		solv(idx+1,Math.abs(now-w[idx]));//추를 구슬과 같이 올린경우
		
	}

}