[AlgoSpot] 달팽이

문제 설명

알고리즘 문제 해결 전략 - 동적 계획법
https://algospot.com/judge/problem/read/SNAIL

문제 풀이

• 조금 생각이 필요한 동적 계획법 문제이다.
• 백트레킹 + 메모이제이션을 이용하여 최적화가 필요하다
• 아래와 같은 점화식을 이용하여 풀이하였다.

climbed(days, climbed) =
days일 이후에 climed만큼 올라갔을 때 m일 이후 n이상 올라가는 확률

climbed(days, climbed) = 0.75climed(days+1, climbed+2) + 0.25climbed(days+1, climbed+1)

소스 코드 (JAVA)

import java.util.Scanner;

public class Main {
    public static int C, N, M;
    public static double result[][];

    public static double solve(int days, int climbed) {
        if (days == M) return climbed >= N? 1.0 : 0.0;
        if (result[days][climbed] != -1) return result[days][climbed];
        double res;
        res = 0.75*solve(days + 1, climbed + 2) + 0.25*solve(days + 1, climbed + 1);
        result[days][climbed] = res;
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        C = sc.nextInt();
        result = new double[1000][];
        for (int i = 0; i < 1000; i++)
            result[i] = new double[2000];
        for (int c = 0; c < C; c++) {
            N = sc.nextInt();
            M = sc.nextInt();
            for (int i = 0; i < M; i++)
                for (int j = 0; j < 2*M + 1; j++)
                    result[i][j] = -1;
            System.out.println(solve(0, 0));
        }
    }
}