[백준 1149] RGB거리

0. 제목

• 백준 1149 RGB거리
• BOJ 1149 RGB거리
• C++ 1149 RGB거리

---

1. 문제

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

---

2. 풀이

• 이웃끼리는 같은 색을 칠할 수 없다.
• RGB를 각각 0번, 1번, 2번 색이라 하겠다.
• 0번색을 칠하면 이웃집은 1, 2가 가능하고 1번색을 칠하면 이웃집은 0, 2가 가능하고 2번색을 칠하면 이웃집은 0, 1이 가능하다.
• arr[i][j]은 i번째 집에 j번 색으로 칠하는 비용이다.
• dp배열의 초기값으로 첫번째 집의 비용을 설정해주었다.
• 그 다음부터 dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0] 와 비슷한 방식으로 1이면 0,2, 2이면 0,1로 설정하여 실행하였다.
• 그렇게 마지막 N번째 loop까지 다 돌고 난 후 N번째에 세가지 색중에 하나로 칠한 각각의 최소비용이 나온다.
• 그 세 개중 최솟값이 모든 집을 칠하는 비용의 최솟값이 된다.

---

3. 코드

#include <iostream>
using namespace std;
 
int N;
int arr[1001][3];
int dp[1001][3];
 
int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i = 1; i <= N; i++)
        cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
    
    dp[1][0] = arr[1][0];
    dp[1][1] = arr[1][1];
    dp[1][2] = arr[1][2];
    for(int i = 2; i <= N; i++){
        dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0];
        dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i][1];
        dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + arr[i][2];
    }
    cout << min(min(dp[N][0], dp[N][1]), dp[N][2]) << '\n';
    return 0;
}