문제링크 : https://www.acmicpc.net/problem/1890
이 문제는 DP문제 입니다. 길을 찾는 방법은 사실 여러가지가 있지만, 조금만 생각해보면 무수히 많은 길을 반복해서 찾아감을 알 수 있었습니다.(DFS로 가든 BFS로 가든, 갔던길을 또 갑니다) 여기에 착안하여 이미 갔던길은 또 가면 안된다는 조건을 걸어둡니다. 마치 옛날 탐험가가 먼저 탐험한 후 이곳엔 원숭이 100마리가 있다고 한것과 같습니다.
음, 위 문단은 제가 막 생각나는대로 작성한 것이고,
DP문제로 풀어야겠다고 마음먹은 이유는 바로, DP는 반복연산을 하지 않게끔 도와주는 알고리즘이므로 격자 내의 한 위치에서 "이 위치에서는 x개의 경로가 있다! " 라는 것을 알려주면 한 위치에서 더이상 가지 않고 " 얘는 x개 경로가 있대~! " 이렇게 말해주는 것 입니다.
소스코드 :
이 문제는 DP문제 입니다. 길을 찾는 방법은 사실 여러가지가 있지만, 조금만 생각해보면 무수히 많은 길을 반복해서 찾아감을 알 수 있었습니다.(DFS로 가든 BFS로 가든, 갔던길을 또 갑니다) 여기에 착안하여 이미 갔던길은 또 가면 안된다는 조건을 걸어둡니다. 마치 옛날 탐험가가 먼저 탐험한 후 이곳엔 원숭이 100마리가 있다고 한것과 같습니다.
음, 위 문단은 제가 막 생각나는대로 작성한 것이고,
DP문제로 풀어야겠다고 마음먹은 이유는 바로, DP는 반복연산을 하지 않게끔 도와주는 알고리즘이므로 격자 내의 한 위치에서 "이 위치에서는 x개의 경로가 있다! " 라는 것을 알려주면 한 위치에서 더이상 가지 않고 " 얘는 x개 경로가 있대~! " 이렇게 말해주는 것 입니다.
소스코드 :
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <string>
using namespace std;
int n;
vector< vector<int> > v(101, vector<int> (101));
vector< vector<long long> > cache(101, vector<long long>(101, -1));
long long DP(long long a, long long b) {
// 도착했으면 1을 반환
if (a == n && b == n) {
return 1;
}
// 기록된게 있으면 기록된걸 반환
if (cache[a][b] != (long long)-1) {
return cache[a][b];
}
// 쌩 처음 와보는 곳임.
// 일단 여기까지 왔으니까 갈수있는 경로의 개수는 0부터 시작(특혜논란)
cache[a][b] = (long long)0;
// 일단 아래방향으로 가본다
long long low = a + (long long)v[a][b];
if (low <= n) {
cache[a][b] += DP(low, b);
}
// 오른쪽으로도 가본다.
long long col = b + (long long)v[a][b];
if (col <= n) {
cache[a][b] += DP(a, col);
}
return cache[a][b];
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> v[i][j];
}
}
long long res = DP(1, 1);
cout << res << endl;
}
| cs |
댓글
댓글 쓰기