[동적 계획법] NUMB3RS 두니발 박사의 탈옥

1. 완전 탐색

 

이 문제는 day만큼 날이 지난다음 q의 마을에 p에서 탈옥한 박사가 있을 확률을 구하는 문제이다.

 

날마다 박사는 인접한곳으로 이동한다.

 

그러므로

 

완전 탐색으로 풀때에는 p에서 시작해서

확률을 곱해가며

모든 경우의 수를 세면서

마지막 날일 때

 

ret[town] += 해당 경우의 확률

 

이처럼 더해가면된다

 

그 후 ret[0] ret[2] 를 호출하게되면 바로 바로 답이 나오게 된다.

 

2. 점화식

이 문제에서 동적 계획법을 적용하려면 완전 탐색 과는 다르게

뒤에서 부터 생각해야한다.

 

FIND(remainDay, startpoint)

= Σ(per(startpoint) * FIND(remainday - 1, next))

remainDay의 날짜가 남았을 떄 startpoint부터 시작하여 교도소까지 도착하는 확률

 

 

 

3. 메모이제이션

 

cache[r][sp] = r의 날짜가 남았을 떄 sp부터 시작하여 교도소까지 도착하는 확률을 리턴하는 배열

 

위와 같은 배열을 만들게 되면 쉽게 함수를 구현할 수 있다.

find()함수의 결과값에 per[q]를 나눈 이유는

동적 계획법을 완전 탐색의 거꾸로 구현했기 때문이다.

함수가 시작하는 q는 마지막 경로이므로 확률을 구할 필요가 없다.

 

 

 

 

#include <iostream>
#include <cstring>
 
int A[100][100];
double cache[101][50];
 
double per[50];
int townN;
int p;
 
double find(int remainDay, int startp)
{
    double &ret = cache[remainDay][startp];
    if(ret != -1.0) return ret;
    if(remainDay == 0) { 
        if(startp == p) return per[startp];
        else return 0;
    }
    ret = 0.0;
    for(int i = 0; i < townN; i++)
        if (A[startp][i] == 1)
            ret = ret + per[startp] * find(remainDay -1, i);
    return ret;
}
 
int main(void)
{
    int testCase = 0, day = 0, t = 0, q = 0;
    scanf("%d",&testCase);
    for(int i = 0; i < testCase; i++)
    {
        scanf("%d%d%d", &townN, &day, &p);
        
        std::fill_n(&cache[0][0],101*50, -1.0 );
        for(int j = 0 ; j < townN ; j++)
        {
            per[j] = 0.;
            for(int k = 0 ; k < townN; k++)
            {
                scanf("%d",&A[j][k]);
                if(A[j][k] != 0)
                    per[j] += 1.0; 
            }
            per[j] = 1.0/per[j];
        }
 
        scanf("%d",&t);
        for(int j = 0; j < t; j++)
        {
            scanf("%d",&q);
            printf("%0.8lf ",find(day,q)/per[q]);
        }
        printf("\n");
    }
}

4. 시간 복잡도 

find 함수는 nd개의 부분문제와 각각 n 시간만큼 수행되므로

총 O(n^2d)라 할 수 있다.

(t번의 함수 실행에 서  중복된 부분은 바로바로 값을 리턴하므로

신경쓰지않아도 된다.)

 

 

 

5. 8장 요약

 

8장의 주된 내용은 메모이제이션을 어떻게 할 것인가? 이다.

거의 모든 문제는 모든 경우의 수를 구하는 순열 문제이고

메모이제이션을 통해 조합 을 구하는 문제로 변형 시켜서

중복된 순서일 경우 O(1)만에 수행되게 만들어 최적화시켰다.

 

6. 마르코프 모델

 

마르코프 연쇄라고 부르는 모델의 성질은 다음과 같다.

 

1. 유한개의 상태

2. 매 시간마다 상태가 변경

3. 어떤 상태 a에서 다른 상태 b로 옮겨갈 확률은 현재 상태 a에만 좌우됨.

   a 이전에 어느 상태에 있었는지, 현재 시간은 얼마인지 등은 영향을 주지않는다.

 

 

NUMB3RS