1편 링크: http://gall.dcinside.com/board/view/?id=programming&no=725837


  이 문제도 동적계획법으로 풀리는 단순한 문제야.
  사실 조금 더 생각해보면 수학적으로 식을 세워서 더욱 효율적으로 해결할 수 있을것 같은데,
  우선 오늘은 밤이 늦어서 그건 연습문제로 남길게(더불어 완전탐색을 동적계획법으로 만들어주는 cache를 코드 가독성상 빼놨어).
  각 방향을 선택할 확률이 모두 같다고 보면(사실 달라도 똑같이 풀리지만), 그냥 단순한 완전 탐색이지.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
double probability_of_alive(int x, int y, int n, int steps_left)
{
    static const vector<int> dx = {-1,  0,  1,  0},
                             dy = { 0, -1,  0,  1};
 
    if (x < 0 || y < 0 || x >= n || y >= n) {
        return 0.0;
    } else if (steps_left == 0) {
        return 1.0;
    }
 
    double answer = 0.0;
 
    for (int dir = 0; dir < 4; dir++) {
        answer += 0.25 * probability_of_alive(x + dx[dir], y + dy[dir], n, steps_left - 1);
    }
 
    return answer;
}
 
double probability_of_alive(int x, int y, int n) {
    return probability_of_alive(x, y, n, n);
}
cs

  N = n이라고 하면

  Additional Space Complexity는 (동적계획법 미적용시) O(1), (동적계획법 적용시) O(n*n*n)

  Time Complexity는 (동적계획법 미적용시) O(4^n) (동적계획법 적용시) O(n*n*n)이 된다.