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

10164번: 격자상의 경로

dp를 이용한 문제이다. 먼저 findO를 통해 주어진 K에 해당하는 좌표를 구해주었다. 그리고 findNM를 이용해 K의 좌표를 끝으로 하는 배열과 K의 좌표가 시작인 배열 두개에서의 dp를 구해주었다. 이때 K가 0이면 findNM을 한번만 사용하였다. dp는 왼쪽 위에서 오른쪽 아래로 이동하기 때문에 경우의 수는 결국 현재의 좌표 바로 위와 왼쪽의 값을 더해준 값이 되게 된다. 즉 점화식은 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]이 된다. 값을 구해준 후 출력해주었다. 쉽게 풀 수 있었던 문제였다.

#include <iostream>

using namespace std;

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

void findNM(int sy, int sx, int ey, int ex) {
    for (int i = sy; i <= ey; i++) {
        for (int j = sx; j <= ex; j++) {
            if (i == sy && j == sx) continue;

            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
}

void findO() {
    if (K == 0) {
        y = N;
        x = M;
        return;
    }

    int index = 1;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (K == index) {
                y = i;
                x = j;

                return;
            }

            index++;
        }
    }
}

void solution() {
    dp[1][1] = 1;

    findO();

    findNM(1, 1, y, x);
    if (K != 0) findNM(y, x, N, M);

    cout << dp[N][M];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M >> K;

    solution();

    return 0;
}