백준 5569, 출근 경로

개요

문제 링크
골드 4, DP
두 칸 이상 이동후 방향 전환을 하며 이동하는 경로의 수

---

접근

1. 경로탐색 문제 중 생각할 여지를 많이 주는 좋은 문제이다. 2차원 dp를 사용하는데 두 가지 조건을 생각하면 되는 문제.

2. 조건을 어기는 상황을 생각하자. 번개모양이 생기면 되는데, 이걸 dp로 어떻게 푸냐? 경로 탐색 dp의 근본부터 다시 생각해야 한다.

   dp[y][x] = dp[y][x-1]+dp[y-1][x]

   보통의 경로탐색 dp는 이렇다. 왼쪽과 아래쪽의 경로 수를 더해준다. 그런데 여기서는 이를 잘 응용해 이렇게 바꾸면 문제가 해결된다.

   dp[y][x].from_left = dp[y][x-1].from_left + dp[y-1][x-1].from_down
   dp[y][x].from_down = dp[y-1][x].from_down + dp[y-1][x-1].from_left

3. 무슨 말인가 하니, (y,x)의 경로의 수는 왼쪽과 아래쪽의 합이었다. 그럼 이를 다시 쪼개서, 왼쪽은 왼왼쪽 (LL)과 왼아 (LD)쪽의 합, 아래쪽은 아왼쪽 (DL)과 아아 (DD)쪽의 합이다. 우리가 피해야 할 부분은?

   LDL에서 LD로 가는 경로와 DLD에서 DL으로 가는 경로이다. 좀 복잡할 수 있는데 천천히 생각해보면 번개모양이 그려짐을 알 수 있다.

4. 그럼 L = LL+LD = LL+LDL+LDD, D = DL+DD = DLL+DLD+DD인데, 우리가 피할 부분은? LDL->LD, DLD->DL이므로 L = LL+LDD, D = DLL+DD를 해주면 된다.
   즉 현재점의 왼쪽 origin = 왼쪽점의 왼쪽 origin, 왼아점의 아래 origin, 현재점의 아래 origin = 아래점의 아래 origin + 왼아점의 왼쪽 origin

---

Pseudo code

dp[y][x] = {
    dp[y][x-1].left + dp[y-1][x-1].down,
    dp[y-1][x].down + dp[y-1][x-1].left
}
answer = dp[y][x].left + dp[y][x].down

---

Source code

#include <iostream>
using namespace std;

#define D 100000
int main() {
    int w, h;
    cin >> w >> h;
    int dp[h+1][w+1][2] = {};
    dp[1][1][0] = 1;
    dp[1][1][1] = 1;

    for (int i=1; i<=h; i++)
        for (int j=1; j<=w; j++) {
            if (i==1&&j==1) continue;
            dp[i][j][0] = (dp[i][j-1][0]+dp[i-1][j-1][1])%D;
            dp[i][j][1] = (dp[i-1][j][1]+dp[i-1][j-1][0])%D;
        }
    cout << (dp[h][w][0]+dp[h][w][1])%D;
}