BOJ : https://www.acmicpc.net/problem/1149

github : https://github.com/junho0956/Algorithm/blob/master/1149/1149/%EC%86%8C%EC%8A%A4.cpp

 

재귀를 통해서 RGB거리에 대한 최소합을 구현하였습니다.

범위를 벗어나면 dp의 최소값을 계속 적용시켜주기 위해 maxi를 반환하였고

범위내에 포함만 된다면 dp값을 계속 확인해가면서 칠할 수 있는 최소값을 저장해두었습니다.

 

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
#include <iostream>
#include <algorithm>
using namespace std;
 
#define maxi 987654321
int dp[1000][3];
int arr[1000][3];
int n;
 
int dfs(int house, int color) {
    if (color < 0 || color > 2return maxi;
    if (house == n - 1return arr[house][color];
 
    int& res = dp[house][color];
    if (res) return res;
 
    res = maxi+10000;
 
    for (int i = 0; i < 3; i++) {
        if (i != color) res = min(res, dfs(house + 1, i));
    }
    res += arr[house][color];
 
    return res;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 3; j++)
            cin >> arr[i][j];
 
    int ans = 987654321;
    for (int i = 0; i < 3; i++) {
        ans = min(ans, dfs(0, i));
    }
 
    cout << ans;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 10995번 별 찍기 - 20  (0) 2020.02.21
BOJ 11654번 아스키 코드  (0) 2020.02.21
BOJ 2941번 크로아티아 알파벳  (0) 2020.02.21
BOJ 15993번 1, 2, 3 더하기 8  (0) 2020.02.20
BOJ 15992번 1, 2, 3 더하기 7  (0) 2020.02.19

+ Recent posts