[BOJ / C++] 1149번 : RGB 거리

문제

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보다 작거나 같은 자연수이다.

출력

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

Solved.ac 레벨

실버 I

풀이

#include <bits/stdc++.h>
#define MAX 1001

using namespace std;

int dp[MAX][4]; //집 별 RGB 비용 1: R, 2: G, 3:B
int n;


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

    cin >> n;

    for(int i = 1; i <= n; i++){
        cin >> dp[i][1] >> dp[i][2] >> dp[i][3];
        
        dp[i][1] = min(dp[i-1][2], dp[i-1][3]) + dp[i][1];
        dp[i][2] = min(dp[i-1][1], dp[i-1][3]) + dp[i][2];
        dp[i][3] = min(dp[i-1][1], dp[i-1][2]) + dp[i][3];
    }

    cout << min(min(dp[n][1], dp[n][2]), dp[n][3]) << '\n';

    return 0;
}

1001개의 건물에 칠할 수 있는 3개의 색을 저장하는 2차원 배열을 이용했다.

조건에서는 i+1 번째의 건물도 고려해야 할 것처럼 설명을 내놨지만, 사실 i번째에서 신경쓸 색은 i-1번째의 색밖에 없다.

i+1번째는 현재 i가 정해진 뒤에 생각해도 문제가 없다.

 

dp배열에 들어가야 하는 값은 값을 칠해왔을 때의 최솟값이다. 따라서 R, G, B 3색에 따라 i-1번째의 색을 칠했을 때 값이 최소가 되는 것을 dp[i]에 넣어줘야 한다.

 

마지막으로는 n번째 건물이 빨간색일 때, 초록색일 때, 파란색일 때 중 가장 작은 최솟값을 출력을 해준다.

 

1149번: RGB거리