우물을 기어오르는 달팽이 (난이도: 하)

1. 문제 설명

(1) 깊이가 N미터인 우물의 맨 밑바닥에 달팽이가 있다.

 

(2) 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에

좌우된다.

 

(3) 날이 맑으면 하루에 2미터를 기어올라갈 수 있지만, 비가 내리면 1미터 밖에 올라가지 못한다.

* 날이 맑거나 비가 올 확률은 각각 50%이다.

 

(4) 앞으로 M일 안에 달팽이가 우물 끝까지 올라갈 확률을 찾는 프로그램을 작성하시오.

 

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

X

 

출력 조건

X

 

 

입력 예제

3
3 5
3 6
5 8

 

출력 예제

0.5

0.125

0.5

 

 

 

 

3. 제약 조건

X

 

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

(1) 지정한 날짜 M까지 도달한 경우

 

 

 

 

6. 코드

public class CLIMB {
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder sb = new StringBuilder();

    // 각각 일 수와 깊이이다.
    private static int M, N;

    private static int[][] cache;

    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        int C = Integer.parseInt(sc.readLine());

        for(int i=0; i<C; i++) {
            cache = new int[101][101];
            st = new StringTokenizer(sc.readLine());

            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            sb.append((solve(0, 0)/Math.pow(2, M))+"\n");
        }
        System.out.println(sb);
    }
    private static int solve(int days, int climbed) {
        // 기저 사례(1): M일이 모두 지난 경우
        if(days==M) return climbed>=N ? 1:0;

        // 메모제이션
        if(cache[days][climbed] != 0) return cache[days][climbed];

        return solve(days+1, climbed+1) + solve(days+1, climbed+2);
    }
}