백준10164 격자상의 경로

작성일 | In

문제 링크

  • http://icpc.me/10164

문제 출처

  • 2014 전국 본선 초등3, 중등1

사용 알고리즘

  • DP

시간복잡도

  • O(nm)

풀이

이 문제는 아마 초등학교 6학년 정도부터 수학 문제에서 상당히 많이 보이는 문제입니다.

로봇은 오른쪽 혹은 아래로만 이동할 수 있습니다.
이 성질을 이용하면 (n, m)까지 가는 경우의 수는 (n-1, m)까지 가는 경우의 수 + (n, m-1)까지 가는 경우의 수라는 사실을 유도해낼 수 있습니다.
재귀 함수로 구현하되, 시간을 줄이기 위해 메모이제이션 기법을 사용합니다.

가능한 상태 공간은 n*m개이며 각각의 상태를 계산할 때 O(1)이 들기 때문에 O(nm)이 걸립니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
using namespace std;

int arr[15][15];
int x, y;

int calc(int n, int m){
	if (n == 1){
		return 1;
	}
	if (m == 1){
		return 1;
	}
	return arr[n][m] = calc(n - 1, m) + calc(n, m - 1);
}

int main(){
	int n, m, k;
	cin >> n >> m >> k;
	int num = 1;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			if (k == num){
				x = i, y = j;
			}
			arr[i][j] = num++;
		}
	}
	if (!k){
		cout << calc(n, m);
	}
	else {
		cout << calc(x, y)*calc(n - x + 1, m - y + 1);
	}
}