[BAEKJOON] 10164 격자상의 경로

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> using namespace std; int row, col; vector<vector<int>>DP(16, vector<int>(16, -1)); int find_way(int x, int y, int end_x, int end_y) { int&ret = DP[x][y]; if (ret != -1) return ret; if (x == end_x && y == end_y) return 1; int num1 = 0, num2 = 0; if (x + 1 <= end_x) num1 = find_way(x + 1, y, end_x, end_y); if (y + 1 <= end_y) num2 = find_way(x, y + 1, end_x, end_y); return ret = num1 + num2; } int main() { int chk, chk_x, chk_y, y; scanf("%d %d %d", &col, &row, &chk); if (chk == 0) { printf("%d", find_way(0, 0, col - 1, row - 1)); return 0; } else { for (y = 1; y <= col; y++) { if (row*y >= chk) { chk_x = y - 1; break; } } chk_y = chk - row*chk_x - 1; printf("%d", find_way(0, 0, chk_x, chk_y)*find_way(chk_x, chk_y, col - 1, row - 1)); } return 0; }