[JAVA] BOJ 백준 4811 알약

방법은 다음과 같다.

1. 이차원 배열에 값을 메모리제이션 할 것이다! → 테스트 케이스가 여러개이므로 값을 최대값인 30(N의 최대값)까지로 선언해준 뒤 다같이 값을 공유하게 한다.
2. d[i][j]는 한 알을 i개, 반 알을 j개 먹는 방법의 수이다. → 즉 W i개, H j개를 가지고 만든 i+j문자열이다.
3. 이때 j는 i보다 클 수는 없다. → 한 알을 먹은 후 반 알이 생기기 때문
4. 이중 for문을 통해 값을 아직 모르는 것은 -1로 불가능 한 값들은 0으로 표기하였다.
5. d[0][0] = 1로 두어 초기값을 준다. d[1][0] = 1로 주어도 된다.
6. d[i][j] = d[i-1][j] + d[i][j]와 같다. 이때 불가능한 값들은 앞에서 0으로 세팅을 해줬기 때문에 신경쓰지 않는다.
7. W<0과 H<0인 경우 불가능 한 값이고 배열에 넣을 수 없기 때문에 0을 return한다.

전체 코드

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

public class Main{
	static long[][] d;
    public static void main(String args[]) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        d = new long[31][31];
        for(int i=0; i<=30; i++) {
        	for(int j=0; j<=30; j++) {
        		d[i][j] = -1;
        		if(i<j || i==0) d[i][j] = 0;
        	}
        }
        d[0][0] = 1;
        int N = 0;
        while((N = Integer.parseInt(bf.readLine()))!=0){
        	System.out.println(find(N, N));
        }
    }
    static long find(int W, int H) {
    	if(W < 0 || H < 0) return 0;
    	if(d[W][H] != -1) return d[W][H];
    	return d[W][H] = find(W, H-1)+find(W-1, H);
    }
}