[백준 - 1149] RGB거리 - C++

분류: dp /

 

문제

문제 링크

문제 설명

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

풀이

#include <iostream>
using namespace std;

inline int min(int x, int y) {return x < y ? x : y;}

int N;
int dp[1000][3];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin >> N;
    for(int i=0; i<N; i++)
        for(int j=0; j<3; j++)
            cin >> dp[i][j];
    
    for(int i=1; i<N; i++){
        dp[i][0] += min(dp[i-1][1], dp[i-1][2]);
        dp[i][1] += min(dp[i-1][0], dp[i-1][2]);
        dp[i][2] += min(dp[i-1][0], dp[i-1][1]);
    }
    cout << min(dp[N-1][0], min(dp[N-1][1], dp[N-1][2]));
    return 0;
}

dp로 바텀업.

열이 3개 뿐이므로 불필요한 덧셈 나머지 연산 대신 직접 더함.

for(int i=1; i<N; i++){
    dp[i][0] += min(dp[i-1][1], dp[i-1][2]);
    dp[i][1] += min(dp[i-1][0], dp[i-1][2]);
    dp[i][2] += min(dp[i-1][0], dp[i-1][1]);
}

for(int i=1; i<N; i++)
    for(int j=0; j<3; j++){
        dp[i][j] += min(dp[i-1][(j+1)%3], dp[i-1][(j+2)%3]);

 

굳이 배열이 필요하지 않음. 입력을 받자마자 바로 계산해도 됨.

#include <iostream>
using namespace std;

inline int min(int x, int y) {return x < y ? x : y;}

int n, R, G, B, r, g, b;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin >> n;
    while(n--){
        cin >> r >> g >> b;
        r += min(G, B);
        g += min(R, B);
        b += min(R, G);
        
        R = r; G = g; B = b;
    }
    cout << min(min(R, G), B);
    return 0;
}