[BOJ/백준][Gold3] 12785 : 토쟁이의 등굣길 (C++)

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

12785번: 토쟁이의 등굣길

 

[난이도] Gold3
[유형] DP

[풀이]
DP[y][x] : y,x에서 출발해서 목적지(ay,ax)로 갈 수 있는 경로의 수
ay,ax를 토스트집의 좌표로 설정한 뒤 DP[1][1]을 구한 값,
ay,ax를 h,w로 설정한 뒤 DP[토스트집의 Y][토스트집의 X]를 구한 값을 곱하면 된다.

1000007로 계산시 나눠줘야 하며 위의 두 값을 곱할 때 int 범위를 넘어갈 수 있으므로
long long으로 계산해야 한다.

 

#include <cstdio>
#include <cstring>
using namespace std;
int w,h,mod=1000007,ax,ay,dp[201][201];

int sol(int y,int x){
    if(y==ay&&x==ax) return 1;

    int& ret = dp[y][x];
    if(ret!=-1) return ret;
    ret=0;
    if(y+1<=h) ret = sol(y+1,x);
    if(x+1<=w) ret += sol(y,x+1);
    return ret%=mod;
}
int main(){
    scanf("%d%d%d%d",&w,&h,&ax,&ay);

    memset(dp,-1,sizeof(dp));
    long long ans=sol(1,1);

    int sy=ay,sx=ax;
    ay=h,ax=w;

    memset(dp,-1,sizeof(dp));
    ans*=sol(sy,sx);
    
    printf("%lld",ans%mod);
}

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