[백준] 13703. 물벼룩의 생존확률

문제 링크

[백준] 13703. 물벼룩의 생존확률

풀이 과정

Top-down 방식의 메모이제이션을 통해 문제를 풀었습니다.

위와 같이 분할 정복을 사용해서 값을 얻어옵니다. 빨간색과 파란색 화살표 경로 설명을 아래에서 하겠습니다.

1. 제일 위에 표시된 위치 2에서 3초가 주어진 물벼룩의 생존 경우의 수를 구하는 메소드로부터, 물벼룩은 1초 뒤 위치 1과 위치 3으로 이동할 수 있습니다.
2. 그 중, 위치 1로 이동한 물벼룩은 2초가 남았고, 다시 위치 0과 위치 2로 이동할 수 있습니다.
3. 그 중, 위치 0으로 이동한 물벼락은 수면에 닿았기 때문에 죽게 됩니다.
4. 위치 2로 이동한 물벼룩은 남은 1초 동안 위치 1과 위치 3으로 이동할 수 있습니다.
5. 위치 1과 위치 3으로 이동한 물벼룩은, 시간을 모두 소요한 채 수면 아래에 위치하므로 생존 가능한 경우에 해당되므로 1을 리턴합니다.
6. 위치 2에 있던 물벼룩은 위 4번에서 얻은 값 2를 리턴합니다.
7. 위치 1에 있던 물벼룩은 위 5번에서 얻은 값 2를 리턴합니다.

위 사진처럼, 같은 파라미터로 메소드가 여러번 호출 되는 것을 확인할 수 있습니다. 그러므로, 불필요한 연산을 다시하지 않도록 메모이제이션을 추가해, 값의 변경이 있었으면 바로 그 값을 리턴하는 방법으로 속도를 향상을 시킬 수 있습니다.

코드

import java.util.Scanner;

public class Main {
    static long[][] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int n = sc.nextInt();
        dp = new long[63 * 2 + 1][n + 1];

        solve(k, n);

        System.out.println(dp[k][n]);
    }

    static long solve(int depth, int time) {
        if (dp[depth][time] != 0) return dp[depth][time];

        if (depth == 0) return 0;
        else if (time == 0) return 1;

        return dp[depth][time] = solve(depth - 1, time - 1) + solve(depth + 1, time - 1);
    }
}