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

문제

출처 : https://www.acmicpc.net/problem/10164

풀이과정

DP[n][m] : (n,m) 까지 올 수 있는 경로의 수를 저장하는 배열

DP[n][m] = DP[n-1][m] + DP[]n][m-1] 라는 점화식 이용

0,0 부터 K값을 가진 x,y 까지의 경로의 수와 x,y 부터 n,m 까지의 경로의 수를 곱하면 답이 된다는 접근까지 했다.

소스코드

#include <iostream>
#include <vector>
 
using namespace std;
 
int DP[16][16]; // 해당 위치까지 올 수 있는 경로의 개수
int N,M,K,point_x,point_y,ans;
 
int main()
{
    int cnt=1,sum_1;
 
    cin >> N >> M >> K;
 
    DP[1][1] = 1;
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (cnt == K) // o자로 표시된 번호의 격자칸 좌표 저장
            {
                point_x = j;
                point_y = i;
            }
            cnt++;
            if (i == 1 && j == 1) continue;
            DP[i][j] = DP[i - 1][j] + DP[i][j - 1];
        }
    }
 
    if (K == 0) cout << DP[N][M];
    else
    {
        sum_1 = DP[point_y][point_x];
 
        DP[point_y][point_x] = 1;
 
        for (int i = point_y; i <= N; i++)
        {
            for (int j = point_x; j <= M; j++)
            {
                if (i == point_y && j == point_x) continue;
                DP[i][j] = 0;
                if (i > point_y) DP[i][j] += DP[i - 1][j];
                if (j > point_x) DP[i][j] += DP[i][j - 1];
            }
        }
        
        cout << sum_1 * DP[N][M];
    }
    return 0;
}