[백준] 4811 알약

www.acmicpc.net/problem/4811

4811번: 알약

2020-01-02

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main4811 {
    public static long dp[][];
 
    public static long init(int w, int h) {
        if(dp[w][h] > 0) return dp[w][h]; // 이미 계산한 적이 있다면
 
        if(w == 0) return 1; // 한 조각이 아예 없는 경우
        
        if(h == 0) return dp[w][h] = init(w-1, h+1); // 반 조각이 없는 경우, (한 조각은 있는 경우)
        else return dp[w][h] = init(w, h-1) + init(w-1, h+1); // 반 조각도 있고(w, h-1) 한 조각도 있는 경우(w-1, h+1)
        
    }
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        dp = new long[31][31];
        init(30, 0);
        while(true) {
            StringTokenizer st = new StringTokenizer(bf.readLine().trim());
            int test = Integer.parseInt(st.nextToken());
            if(test == 0) break;
            System.out.println(dp[test][0]);
        }
    }
}
 

아이디어가 생각이 안 나서 힌트를 얻어서 푼 문제이다.

 

#문제풀이

1일차, 2일차, 3일차에 알약을 먹을 수 있는 문자열들은 다음과 같다.

 

dp 2차원 배열을 만들고 앞 부분은 w의 개수, 뒤에는 h의 개수라고 놓는다. 그림과 같이 베이스가 되는 알약의 개수 dp[0][1]을 찾을 때까지 탐색하고 거꾸로 더해 dp[약의개수][0] 의 값을 찾으면 된다. 

 

(1) 이미 계산한 적이 있다면 dp[w][h] 값을 리턴해주면 되고 

(2) w == 0 인 경우는 우리가 찾는 base 이므로, 1을 리턴해준다.

(3) h == 0 인 경우는 반조각이 하나도 없으므로 한 조각을 사용해야해서 (w-1, h+1) 이 된다.

(4) 그 외의 경우에는 반조각이 있는 경우 (w, h-1)와 한 조각과 반 조각 모두 있는 경우 (w-1, h+1) 가 있다.