장마가 찾아왔다 (난이도: 하)

( 이 알고리즘은 아래 링크에 이어서 진행됩니다. )

 

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

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

 

1. 문제 설명

(1) 앞의 문제에서는 날이 맑거나 비가 올 확률은 동일하게 50%의 확률을 가졌다.

 

(2) 그러나 여기서는 비가 올 확률을 50%에서 75%로 올라갔다고 가정한다.

 

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

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

X

 

출력 조건

X

 

 

입력 예제

4
5 4
5 3
4 2
3 2

 

출력 예제

0.99609375
0.84375
0.5625
0.9375

 

 

 

 

3. 제약 조건

X

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

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

 

 

 

 

6. 코드

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

    private static int N, M;

    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());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            sb.append((solve(0, 0))+"\n");
        }
        System.out.println(sb);
    }

    private static double 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 0.25*solve(days+1, climbed+1) + 0.75*solve(days+1, climbed+2);
    }
}

 

 

 

7. 점화식

- 앞 문제(우물을 기어오르는 달팽이)에서는 모든  경우의 수를 계산하여 확률을 구했다면, 이 문제에서는 재귀 호출

할 때마다 직접 확률을 구한다.