BOJ::1149 RGB거리

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


다이나믹프로그래밍 문제이다.

i번째 집이 빨강,파랑,초록일 경우 각각 최소값이 오도록 2차원배열을 만들었다


ex)

i번째 집을 빨강으로 칠할 경우 : 

i번째집을 빨강으로칠하는 비용 + min(i-1번째집을 파랑으로 칠한경우, i-1번째 집을 초록으로 칠한 경우)


JAVA


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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class Main{
    static int n;
    static int d[][];
    static RGB list[];
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(br.readLine());
        d=new int[n+1][3];
        list = new RGB[n+1];
        
        for(int i = 1 ; i <= n ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list[i]=new RGB(r,g,b);
        }
        
        d[1][0]=list[1].r;
        d[1][1]=list[1].g;
        d[1][2]=list[1].b;
        
        for(int i = 2 ; i <= n ; i++){
            d[i][0]=list[i].r+min(d[i-1][1],d[i-1][2]);
            d[i][1]=list[i].g+min(d[i-1][0],d[i-1][2]);
            d[i][2]=list[i].b+min(d[i-1][0],d[i-1][1]);
        }
        
        System.out.println(min(min(d[n][0],d[n][1]),d[n][2]));
    }
    public static int min(int a,int b){
        if(a<b){
            return a;
        }
        return b;
    }
}
//3가지 색 저장할 클래스
class RGB{
    int r;
    int g;
    int b;
    RGB(int _r, int _g, int _b){
        r=_r;
        g=_g;
        b=_b;
    }
}
cs


C++


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
#include <iostream>
using namespace std;
 
int min(int a, int b) {
    if (a < b) {
        return a;
    }
    return b;
}
 
int main() {
    int n;
    int d[1001][3];
    int a[1001][3];
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        int r, g, b;
        cin >> r >> g >> b;
        a[i][0] = r;
        a[i][1] = g;
        a[i][2] = b;
    }
 
    d[0][0] = a[0][0];
    d[0][1] = a[0][1];
    d[0][2] = a[0][2];
 
    for (int i = 1; i < n; i++) {
        d[i][0] = a[i][0] + min(d[i - 1][1], d[i - 1][2]);
        d[i][1] = a[i][1] + min(d[i - 1][0], d[i - 1][2]);
        d[i][2] = a[i][2] + min(d[i - 1][0], d[i - 1][1]);
    }
 
    cout << min(d[n - 1][2], min(d[n - 1][0], d[n - 1][1])) << endl;
}
cs


저작자표시

'BOJ::문제풀이' 카테고리의 다른 글

1157 단어 공부  (0) 2017.12.30
1152 단어의 개수  (0) 2017.12.30
1065 한수  (0) 2017.12.30
1049 기타줄  (0) 2017.12.30
1012 유기농배추  (0) 2017.12.30

+ Recent posts

티스토리툴바