문제

문제 링크

문제 접근

  • 이 문제에서 움직이는 방향은 우, 하 이렇게 두 경우만 존재하기 때문에 두 지점 사이에는 사이클은 허용되지 않고 최단 경로만 허용된다.
  • 때문에 맨위에부터 차근차근 갈 수 있는 경우의 수를 dp에 저장하고 이를 이용해서 모든 경로를 구할 수 있다.
  • 먼저 시작점부터 X까지의 직사각형 내에 있는 경로들로만 경우의 수를 구한다.
  • 그리고 나서 X에서 끝지점까지 직사각형 내에 있는 경우의 수를 다시 구하면 끝지점에 정답이 저장된다.
  • 만일 K가 0이라면 그냥 시작점부터 끝지점까지의 모든 경우의 수를 구하면 된다.

코드

#include <cstdio>
int x, y, n, m, k, dp[16][16];
int main(){
    scanf("%d %d %d", &n, &m, &k);     
    dp[0][0] = 1; 
    x = (k - 1) / m, y = (k - 1) - x * m;
    if(k != 0){
        for(int i = 0; i <= x; i++){
            for(int j = 0; j <= y; j++){
                if(i + 1 <= x)dp[i + 1][j] += dp[i][j];
                if(j + 1 <= y)dp[i][j + 1] += dp[i][j];
            }
        }
    }
    else x = 0, y = 0;
    for(int i = x; i < n; i++){
        for(int j = y; j < m; j++){
            if(i + 1 < n)dp[i + 1][j] += dp[i][j];
            if(j + 1 < m)dp[i][j + 1] += dp[i][j];
        }
    }
    printf("%d", dp[n - 1][m - 1]);
}