백준 10164 - 격자상의 경로(C++)

문제 링크입니다. https://www.acmicpc.net/problem/10164

10164번: 격자상의 경로

격자가 주어지고 중간에 무조건 거쳐야할 점이 주어질 때, 총 경우의 수를 구하는 문제입니다.

 

수학 중 경우의 수 문제를 풀 때, 한번씩은 풀어봤을 문제입니다.

 

(X, Y)번 격자를 갈 때의 경우의 수는 다음과 같이 구해집니다.

1	1	1	1	1
1	1+1	2+1	...	...
1	2+1	3+3	...	...
1	3+1	4+6	...	...

따라서 (X, Y) = (X-1, Y) + (X, Y-1) 이 된다고 할 수 있습니다.

 

무조건 거쳐하는 점이 있을 경우에는 해당 점에서 다시 시작한다고 생각할 수 있습니다.

 

따라서 크기가 (N-x+1, M-y+1)의 격자를 따로 구하면 되는 것입니다. 

 

dp[N][M]을 (N, M)까지 가는 경우의 수라고 생각했을 때,

 

중간에 거쳐야하는 점(x,y)이 있는 경우는

dp[x][y] * dp[N-x+1][M-y+1]의 값이 됩니다.

 

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#define INF 987654321

using namespace std;

int N, M, K;
int dp[16][16];
int x, y;

void solve(){
    x = K / M + 1;
    y = K % M;
    if(y == 0) {
        y = M;
        x -= 1;
    }
    dp[1][1] = 1;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(i == 1 && j == 1) continue;
            else dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    if(K != 0){
        cout << dp[x][y] * dp[N - x + 1][M - y + 1];
    }
    else{
        cout << dp[N][M];
    }
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M >> K;
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.