Beakjoon 1149 RGB거리

12 Jan 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/1149

나의 풀이

아래 표는 i번째 집의 빨강, 초록, 파랑으로 칠하는 비용을 나타낸 것이며 각 생의 표기는 편의상 R, G, B로 표현하였다.

i	R	G	B
i = 1	26	40	83
i = 2	49	60	57
i = 3	13	89	99

먼저 i=2 일 때 최솟값을 구해보자.
2번째 집을 칠하는 방법은 R, G, B 총 세가지 경우가 있다.
2번째 집의 색을 R로 정했을 때 최솟값 S2_R은
\(S2_R = min(G_1, B_1) + R_2\)로 표현된다.
이 식에서 R_i 는 i번째 집의 빨강 비용, G_i는 i번째 집의 초록 비용, B_i는 i번째 집의 파랑 비용을 의미한다. 또한 min(A,B)는 A와 B중 더 작은 값을 의미한다.
마찬가지로 G로 정했을 때와 B로 정했을 때의 최솟값은
\(S2_G = min(R_1, B_1) + G_2\),
\(S2_B = min(R_1, G_1 ) + B_2\) 로 표현하여 각각 아래와 같은 결과를 얻을 수 있다.

S2_R = min(40, 83) + 49 = 89
S2_G = min(26, 83) + 60 = 86
S2_B = min(26, 40) + 57 = 83

2번 집에서의 총 최솟값은 min(S_R, min(S_G, S_B))로 표현할 수 있고 min(89, min(86, 83)) = 83이라는 것을 구할 수 있다.

마찬가지로 3번째 집의 색을 R, G, B 각각의 색으로 정했을 때 최솟값을 구해보자

S3_R = min(S2_G, S2_B) + R_3 = 83 + 13 = 96
S3_G = min(S2_R, S2_B) + G_3 = 83 + 89 = 172
S3_B = min(S2_R, S2_G) + B_3 = 86 + 99 = 185
3번 집에서의 최솟값 = 96

이제 이 과정을 일반화 시켜보자 DP[i][j]는 i번째 집의 색을 j로 정했을 때 최솟값을 의미한다. 이 때 j의 값은 R=0, G=1, B=2이다.
위에서 각 색상을 선택했을 때의 최솟값 S2_R, S2_G, S2_B를 각각 DP[2][0], DP[2][1], DP[2][2]로 표현할 수 있다.
DP[i][0] = min(DP[i-1][1], DP[i-1][2]) + R_i
DP[i][1] = min(DP[i-1][0], DP[i-1][2]) + G_i
DP[i][2] = min(DP[i-1][0], DP[i-1][1]) + B_i
i번 집에서의 최솟값 = min(DP[i][0], min(DP[i][1], DP[i][2]))

풀이 코드 : 1149 RGB거리

#include <stdio.h>
#include <vector>


using namespace std;

vector<int> RGB[1000];
int DP[1000][3];


int main(){
    int N, r, g, b;
    scanf("%d",&N);
    for(int i = 0;i<N;i++){
        scanf("%d %d %d", &r, &g, &b);
        RGB[i].push_back(r);
        RGB[i].push_back(g);
        RGB[i].push_back(b);
    }

    DP[0][0] = RGB[0][0];
    DP[0][1] = RGB[0][1];
    DP[0][2] = RGB[0][2];


    for(int i = 1;i<N;i++){
        DP[i][0] = min(DP[i-1][1], DP[i-1][2]) + RGB[i][0];
        DP[i][1] = min(DP[i-1][0], DP[i-1][2]) + RGB[i][1];
        DP[i][2] = min(DP[i-1][0], DP[i-1][1]) + RGB[i][2];
    }
    int answer = min(DP[N-1][0], min(DP[N-1][1], DP[N-1][2]));
    printf("%d",answer);
}

채점결과