[백준] 10164번 격자상의 경로

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

문제

입출력

문제 접근

dp문제이다.
내가 풀었던 방법이 맞지 않아, 다른 블로그를 참고하였다.
해당 문제의 점화식은 다음과 같다.
dp[i][j] = dp[i-1][j] + dp[i][j-1]
여기서 k가 0일때와 그렇지 않을 때를 나누고,
만약 0이 아니면, K보다 좌표가 큰 것들을 다시 계산해주고, K까지의 값과 곱해준다.

코드 구현(c++)

#include <iostream>
#include <cstring>

using namespace std;
int N, M, K;
int cache[226];
int dp[16][16];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> N >> M >> K;
    int cnt = 0;
    
    int mid_x, mid_y;
    memset(cache,-1,sizeof(cache));
    memset(dp,0,sizeof(dp));
    dp[1][1] = 1;
    for(int i = 1; i <= N ; i++){
        for(int j = 1 ; j <= M ; j++){
            cnt++;
            if(cnt == K){
                mid_y = i; mid_x = j;
            }
            if(i == 1 && j == 1) continue;
            // dp[i][j] = dp[i-1][j] + dp[i][j-1];
            if(i-1 >= 1) dp[i][j] += dp[i-1][j];
            if(j-1 >= 1) dp[i][j] += dp[i][j-1];
        }
    }
    if(K == 0)cout << dp[N][M] << "\n";
    else{
        int mid_result = dp[mid_y][mid_x];
        dp[mid_y][mid_x] = 1;
        for(int i = mid_y ; i <= N ; i++){
            for(int j = mid_x ; j <= M ; j++){
                if(i == mid_y && j == mid_x)continue;
                dp[i][j] = 0;
                if(i > mid_y) dp[i][j] += dp[i-1][j];
                if(j > mid_x) dp[i][j] += dp[i][j-1];
            }
        }
        cout << mid_result * dp[N][M] << "\n";
    }
}