[BOJ] 17404 RGC거리 2

Time Lapse :12min 50sec

17404.cpp

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
#include <iostream>
#include <memory.h>
using namespace std;
int cost[1000][3], n, dp[1000][3], start;
int dpf(int cur, int color) {
if(dp[cur][color] != -1) return dp[cur][color];
if(cur == n - 1)
return color == start ? 987654321 : cost[cur][color];
dp[cur][color] = 987654321;
for(int i = 0; i < 3; i++)
if(color != i)
dp[cur][color] = min(dp[cur][color], dpf(cur+1, i));
return dp[cur][color] += cost[cur][color];
}
int main() {
scanf("%d",&n);
for(int i = 0; i < n; i++)
scanf("%d %d %d",&cost[i][0], &cost[i][1], &cost[i][2]);
memset(dp, -1, sizeof(dp));
int ans = 987654321;
for(; start < 3; ++start) {
memset(dp, -1, sizeof(dp));
ans = min(ans, dpf(0, start));
}
printf("%d\n",ans);
}
Author: Song Hayoung
Link: https://songhayoung.github.io/2020/09/11/PS/BOJ/17404/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.