백준 4811 - 알약

Java

4811 번 - 알약

문제

접근 방법

먼저 w와 h로 만들 수 있는 서로 다른 문자열의 개수를 구해보자.
DP[W][H]를 큰 알약 W개와 작은 알약 H개로 만들 수 있는 서로 다른 문자열의 경우의 수이다.
만약 H가 0이고 W가 1부터 증가하면,

dp[1][0] = 1       ->  'W'
dp[2][0] = 1       ->  'WW'
...
dp[n][0] = 1       ->  'WWW ...  WW'

가 된다.
W으로만 만들 수 있는 서로 다른 문자열은 하나 밖에 없기 때문이다.

그럼 H로만 만들 수 있는 문자열도 하나로 동일하다.

dp[0][1] = 1       ->  'H'
dp[0][2] = 1       ->  'HH'
...
dp[0][n] = 1       ->  'HHH ...  HH'

만약 W와 H가 각각 1개씩일 때 만들 수 있는 서로다른 문자열은 무엇일까?

dp[1][1] = 2 	-> 'WH', 'HW'이다.  

그럼 W가 2, H가 1로 만들 수 있는 문자열은?

dp[2][1] = 3       ->  'WWH', 'WHW', 'HWW'  

즉 위 패턴을 보면, ‘W’와 ‘H’로 표현할 수 있는 길이가 N인 문자열 = ‘W’와 ‘H’로 표현할 수 있는 길이가 N - 1인 문자열 + ‘W’ or ‘H’ 이다!

위 방식으로 dp[n][n]를 구하면 될 것 같지만, 문제의 제일 중요한 조건이있다.

처음에 반드시 한 조각 W가 나와야 하므로, H가 제일 처음 나오는 문자열은 존재 할 수 없다.
따라서, 위 dp를 만드는 조건에서 H가 처음 나오는 값은 다 0으로 생각하여야한다.

dp[0][1] = 0      
dp[0][2] = 0   
...
dp[0][n] = 0 

이에 H가 W보다 많은 경우는 반드시 H가 먼저 시작하게 되는 경우가 존재하므로 0이다.

코드

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

public class Main {
	static int n, tc, result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	long[][] dp;
    	
    	while(true) {
    		n = stoi(br.readLine());
    		if(n == 0)
    			break;
    		dp = new long[31][31];
			// w로만 만들어 지는 서로 다른 문자열의 개수는 1이다.
    		for(int i = 1; i <= 30; i++)
    			dp[i][0] = 1;
    		
    		for(int i = 1; i <= 30; i++) {
    			for(int j = 1; j <= 30; j++) {
					// 만약 H가 W보다 많은 경우는 존재 할 수 없다.  
    				if(j > i)
    					break;
    				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    			}
    		}
    		
    		System.out.println(dp[n][n]);
    	}
    	
    	br.close();
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

2개의 알파벳으로 만들 수 있는 서로 다른 문자열의 경우의 수를 구하는 것이 핵심인 문제였다.

개선할 점