1149 RGB 거리
알고리즘(dp)
1
2
1. 그냥 현재 노드에서 이전의 상태가 X였을때의 최솟값을 저장하는 dp 배열 DP[1000][3] 을 선언하고 DP를 해주면 된다.
2. 첫번째와 마지막이 상관이없으므로 매번 값을 초기화 시켜줄 필요는 없다.
코드
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
#include <iostream>
#define INF 2000000000
using namespace std;
int N, cost[1000][3], DP[1000][3];
int getMin(int deep, int bf);
int min(int a, int b) {
return a < b ? a : b;
}
int main() {
cin >> N;
for (int i = 0; i < N; i++)
cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
int result = INF;
for (int i = 0; i < 3; i++) {
result = min(result, getMin(1, i) + cost[0][i]);
}
cout << result;
}
int getMin(int deep, int bf) {
if (deep == N) {
return 0;
}
if (DP[deep][bf] != 0)
return DP[deep][bf];
int result = INF;
for (int i = 0; i < 3; i++)
if (i != bf)
result = min(result, getMin(deep + 1, i)+ cost[deep][i]);
return DP[deep][bf] = result;
}