[BOJ/백준][Gold4] 5569 : 출근 경로 (C++)

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

5569번: 출근 경로

 

 

[난이도] Gold4
[유형] DP

[풀이]
아래와 같은 정의 4차원 dp를 이용하면 해결이 가능합니다.
이전 상태와, 현재 방향을 각각 f,d에 저장했습니다.
dp[y][x][f][d] : 현재 방향이 d (0:세로, 1:가로) 이고, 이전 이동 상태가 f (0:방향 변경x 1:방향 변경o) 이면서
                 현재 위치가 (y,x)일 때, (h,w)까지 도달하는 경우의 수.

 

 

#include <cstdio>
#include <cstring>
int w,h,dp[101][101][2][2];
int sol(int y,int x,int f,int d){
    if(y>h||x>w) return 0;
    if(y==h&&x==w) return 1;
    int& ret = dp[y][x][f][d];
    if(ret!=-1) return ret;
    if(d==0){
        ret=sol(y+1,x,0,0);
        if(!f) ret = (ret+sol(y,x+1,1,1))%100000;
    }else{
        ret=sol(y,x+1,0,1);
        if(!f) ret = (ret+sol(y+1,x,1,0))%100000;
    }
    return ret;
}
int main(){
    scanf("%d%d",&w,&h);
    memset(dp,-1,sizeof(dp));
    printf("%d",(sol(2,1,0,0)+sol(1,2,0,1))%100000);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/5569.cpp