[백준/c++] 1149번: RGB 거리

 

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

1149번: RGB거리

 

 

N개의 집이 있고, 1부터 N까지 순서대로 집이 나열되어있다.

모든 집을 RGB 중 하나의 색상으로 칠하는데 드는 최소 비용을 출력하는 문제이다. RGB 색상을 고르는 것에는 규칙이 존재한다.

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

이 규칙은 한마디로 앞의 집과 동일한 색을 칠하지 않는 것이다.

 

이 문제는 dp로 풀 수 있는데, i개의 집을 칠하는 최소 비용을 구하고 점차 개수를 늘려서 N개의 집을 칠하는 최소 비용을 구하면 된다.

여기서, 만약 1번 집에서 최소 비용인 색상 R을 선택했다고 가정해보자. 그러면 2번 집에서는 R을 제외한 G, B를 선택해야 하는데 1번의 R의 비용과 G, B를 더한 비용이 1번의 B(1번 집의 최소비용이 아님)와 2번의 R을 선택한 비용보다 크다면? 2개의 집을 칠하는데 드는 비용이 최소 비용이 되지 않는다.

 

그러므로, 2번 집에서 R을 선택했을 경우, 발생하는 비용(1번 집은 G or B 선택)

G을 선택했을 경우, 발생하는 비용(1번 집은 R or B 선택)

B을 선택했을 경우, 발생하는 비용(1번 집은 G or R 선택)

 

을 dp 2차원 배열에 넣어줘서 진행하도록 한다. 마지막 출력을 N개의 집을 칠하는데 드는 최소 비용을 구하면 되므로

N번째 집에서 R, G, B 중 하나를 선택했을 때 발생하는 최종 최소 비용을 출력하면 된다.

 

 

#include <iostream>
#include <algorithm>
#define num 1002
using namespace std;
int n, home[num][4], dp[num][4];

void input(){
    cin >> n;
    for(int i=1; i<=n; i++) for(int j=1; j<=3; j++) cin >> home[i][j];
}

void solution(){
    dp[1][1] = home[1][1]; dp[1][2] = home[1][2]; dp[1][3] = home[1][3]; //초기값
    
    for(int i=2; i<=n; i++){
        dp[i][1] = home[i][1] + min(dp[i-1][2], dp[i-1][3]);
        dp[i][2] = home[i][2] + min(dp[i-1][1], dp[i-1][3]);
        dp[i][3] = home[i][3] + min(dp[i-1][2], dp[i-1][1]);
    }
    
    cout << min(min(dp[n][1],dp[n][2]), dp[n][3]) << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!