[백준(Baekjoon)][자바(java)] 2629 : 양팔저울 / 동적 계획법 2

 

www.acmicpc.net/problem/2629

2629번: 양팔저울

 

문제 풀이

 

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

public class Main {
	
	public static void dp_recursion( int i, int ws, int nw, int w[], boolean dp[][] ) {
		if( i > nw || dp[i][ws] )  return;
		dp[i][ws] = true;
		dp_recursion( i + 1, ws, nw, w, dp );
		dp_recursion( i + 1, ws + w[i], nw, w, dp );
		dp_recursion( i + 1, Math.abs( ws - w[i] ), nw, w, dp );
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		int nw = Integer.parseInt( br.readLine() ), i;
		int w[] = new int[nw+1];
		StringTokenizer st = new StringTokenizer( br.readLine() );
		for( i = 0; i < nw; i++ )
			w[i] = Integer.parseInt( st.nextToken() );
		int nb = Integer.parseInt( br.readLine() );
		int b[] = new int[nb], mb = 15000;
		st = new StringTokenizer( br.readLine() );
		for( i = 0; i < nb; i++ )
			b[i] = Integer.parseInt( st.nextToken() );
		br.close();
		
		boolean dp[][] = new boolean[nw+1][mb+1];
		dp_recursion( 0, 0, nw, w, dp );
		
		StringBuilder sb = new StringBuilder();
		for( i = 0; i < nb; i++ ) 
			sb.append( ( b[i] <= mb && dp[nw][b[i]] ? "Y" : "N" ) + " " );
            
		System.out.println( sb.toString() );
	}
}

 

*  동적 계획법

-  예제와 같이 무게가 각각 1, 4인 추 2개로 확인할 수 있는 구슬의 무게는 1, 4, Math.abs( 1-4 ), 1+4  이다.
-  2차원 dp 배열 생성 ( boolean 타입 )
   dp[i][j] => i 번째 추까지 포함하여 무게가 j인 구슬을 확인할 수 있는가? 
-  recursive 함수로 무게가 w[i]이거나, w[i]+w[i+1]이거나, abs( w[i]-w[i+1] )일 경우 dp[i][j]에 true를 대입