[백준(Baekjoon)][자바(java)] 4811 : 알약 / 동적 계획법

 

www.acmicpc.net/problem/4811

4811번: 알약

 

문제 풀이

 

 

▶  재귀  -->  시간 초과

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

public class Main {		// 시간 초과
	
	static int cnt;
	
	public static void dfs_cntWay( int w, int h ) {
		if( w == 0 ) {
			cnt++;
			return;
		}
		dfs_cntWay( w-1, h+1 );
		if( h > 0 )
			dfs_cntWay( w, h-1 );
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		StringBuffer sb = new StringBuffer();
		int n;
		while( true ) {
			n = Integer.parseInt( br.readLine() );
			if( n == 0 )
				break;
			cnt = 0;
			dfs_cntWay( n, 0 );
			sb.append( cnt + "\n" );
		}
		br.close();
		
		System.out.println( sb.toString() );

	}
}

 

▶  재귀 + 동적 계획법

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

public class Main {
	
	static long dp[][] = new long[31][31];
	
	public static long dfs_dp_cntWay( int w, int h ) {
		if( w == 0 )
			return 1;
		if( dp[w][h] > 0 )
			return dp[w][h];
		dp[w][h] = dfs_dp_cntWay( w-1, h+1 );
		if( h > 0 )
			dp[w][h] += dfs_dp_cntWay( w, h-1 );
		return dp[w][h];
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		StringBuffer sb = new StringBuffer();
		int n;
		while( true ) {
			n = Integer.parseInt( br.readLine() );
			if( n == 0 )
				break;
			sb.append( dfs_dp_cntWay( n, 0 ) + "\n" );
		}
		br.close();
		
		System.out.println( sb.toString() );
        
	}
}

 

w = 한 알
h = 반 알

< 병에서 약을 꺼내는 방법 >
1. 한 알을 꺼내 반을 쪼갠 후 먹고 나머지 반 알은 다시 병에 넣기  ( w-1, h+1 )
2. 반 알을 꺼내기  ( h-1 )

w, h 의 각각의 개수에 따른 '가능한 서로 다른 문자열의 개수'( 약을 꺼내는 경우의 수 )를 담을 2차원 dp 배열 생성