[백준 5569번] 출근 경로 (C++)

문제링크 : https://www.acmicpc.net/problem/5569

5569번: 출근 경로

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

#define MOD 100000
int dp[101][101][4]; //방향이 총 4가지

int main()
{
   int W, H;
   cin >> W >> H;

   for(int i=1; i<=H; i++)
   {
      dp[i][1][0] = 1; //위 -> 위
   }

   for(int i=1; i<=W; i++)
   {
      dp[1][i][2] = 1; //오른쪽 -> 오른쪽
   }

   for(int i=2; i<=H; i++)
   {
      for(int j=2; j<=W; j++)
      { 
         dp[i][j][0] = (dp[i-1][j][0] + dp[i-1][j][1])%MOD; //위 -> 위 || 오른쪽 -> 위
         dp[i][j][1] = dp[i-1][j][2]; //오른쪽 -> 위 (오른쪽으로 오는 경우)

         dp[i][j][2] = (dp[i][j-1][2] + dp[i][j-1][3])%MOD; //오른쪽 -> 오른쪽 || 위 -> 오른쪽
         dp[i][j][3] = dp[i][j-1][0]; //위 -> 오른쪽 (위쪽으로 오는 경우)
      }
   }

   cout << (dp[H][W][0] + dp[H][W][1] + dp[H][W][2] + dp[H][W][3])%MOD;
}

경우의 수는 아래와 같이 총 4가지가 있다.

위 -> 위
위 -> 오른쪽
오른쪽 -> 오른쪽
오른쪽 -> 위

 

 

첫 1행 1열은 위로만 가는 경우(열)와 오른쪽으로 가는 경우(행)를 1로 초기화해준다.

방향은 그대로 이어지므로 해당 줄은 1로 초기화가 된다.

 

이제 이를 토대로 dp를 채워나간다.

이제 위로 간다고 가정할때, 그전에 이미 위에서 오다가 또 위로 갈수도 있고, 아니면 오른쪽에서 오다가 위로 갈 차례일 수도 있다.

따라서  위 -> 위와 오른쪽 -> 위의 경우 2가지를 모두 고려해야한다.

이때 오른쪽 -> 위의 경우 방향이 달라지므로 경우의 수가 추가된다.

그전의 오른쪽으로 올때 이 오른쪽의 또 전에 오른쪽 -> 오른쪽인지, 위 -> 오른쪽인지도 확인해줘야한다.

위 -> 위의 경우는 방향이 달라지지 않기에 이런 것을 고려하지 않아도 된다.

 

오른쪽 -> 오른쪽, 위 -> 오른쪽의 경우도 위와 같다.

위 -> 오른쪽만 방향이 달라지기에 위로 가기전에 또 위->위와 오른쪽->위의 경우의 수를 체크해줘야한다.