[BOJ/C++] 5569 - 출근 경로

https://www.acmicpc.net/problem/5569

---

 

모든 경우에 대해서 탐색하려고 하면,

최대 200C100의 경우의 수가 만들어지므로 시간 안에 해결할 수 없습니다.

 

 

해당 문제는 dp로 해결할 수 있습니다.

현재칸에 위/왼쪽에서 왔고, 방향을 바꿀 수 있는지에 대한 여부를 기록하기 위해 dp[i][j][k][l]로 표현할 수 있습니다. 

i, j : 현재 칸의 인덱스

k : 0이라면 왼쪽에서, 1이라면 위에서 접근

l : 0이라면 방향을 바꿀 수 없고, 1이라면 방향을 바꿀 수 있음

 

 

 

 

점화식은 위 그림처럼 나타낼 수 있습니다. (파란색, 연두색)

빨간색은 {i,j}에 접근하는 모든 경우입니다.

이전 칸에서 한번 꺾은(방향을 바꾼) 경우엔 {i,j}에서는 방향을 바꿔선 안되고,

반대로 꺾지 않은 경우엔 {i,j}에서 방향을 바꿀 수도 있고, 안 바꿀 수도 있습니다.

 

 

이때 초기화는 {1,1}에서는 어느 방향을 가던 상관 없기 때문에

dp[1][1][0][1] = dp[1][1][1][1] = 1로 합니다.

---

코드

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*----------------------*/

const int MX = 100;
const int MOD = 100'000;
ll dp[MX+2][MX+2][2][2]; //{i,j}에 왼쪽/위 방향에서, 꺾기 불가능/가능
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n,m; cin>>n>>m;

    dp[1][1][0][1] = dp[1][1][1][1] = 1;

    REP(i,1,n){
        REP(j,1,m){
            if(i==1&&j==1) continue;
            dp[i][j][0][0] = (dp[i-1][j][0][0] + dp[i-1][j][0][1])%MOD;
            dp[i][j][0][1] = dp[i-1][j][1][0]%MOD;
            dp[i][j][1][0] = (dp[i][j-1][1][0] + dp[i][j-1][1][1])%MOD;
            dp[i][j][1][1] = dp[i][j-1][0][0]%MOD;
        }
    }

    ll ans = 0;
    REP(i,0,1) REP(j,0,1) ans+=dp[n][m][i][j];
    cout<<ans%MOD<<'\n';
    
}