[C++]백준 - 1149번 문제

1149번: RGB거리 (acmicpc.net)

1149번: RGB거리

 

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보다 작거나 같은 자연수이다.
• 출력
• 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

입력

---

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

 

 

출력

---

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

 

 

 

---

 

생각해 볼 점

---

동적 계획법, 재귀의 경우에는 점화식을 찾는 것이 중요합니다.

 

x(n) = { if(n ==1 ) max(R[1], G[1], B[1]); }

         { if(n > 1) max(

          max( R[n] + G[n-1], R[n] + B[n-1]),

          max( G[n] + R[n-1], G[n] + B[n-1]),

          max( B[n] + R[n-1], B[n] + G[n-1]))}

 

RGB를 각각 택했을 경우의 최대값을 DP 배열에 저장해 두겠습니다.

R을 택했을 때, G를 택했을 때, B를 택했을 때의 최댓값을 따로 저장하여 연산 과정을 줄이도록 합니다.

 

코드

---

#include <iostream>
using namespace std;

#define INT_MAX 2147483647;

int dp[1001][3] = {0,};
int RGB[1001][3] = {0,};

int solution(int index, int sel)	//sel = R, G, B의 선택
{
    if(index == 0) return RGB[0][sel];
    if(dp[index][sel] != 0) return dp[index][sel];
    int min = INT_MAX;
    for(int i = 0; i < 3; i++)
    {
        if(i == sel) continue;	//선택한 색상의 경우 연속해서 선택할 수 없음
        int result = RGB[index][sel] + solution(index - 1, i);
        if(result < min) min = result;
    }
    dp[index][sel] = min;
    return min;
}


int main()
{
    int N;
    cin >> N;
    for(int i = 0; i < N; i++) cin >> RGB[i][0] >> RGB[i][1] >> RGB[i][2];
    int R = solution(N-1, 0);
    int G = solution(N-1, 1);
    int B = solution(N-1, 2);
    int result = R;
    if(G < result) result = G;
    if(B < result) result = B;
    cout << result;
    return 0;
}

 

그 외

---

요즘 들어 동적 계획법이 유독 어렵게 느껴집니다. 저에게 잘 안맞는 알고리즘일지도 모르겠네요.