[백준] 1149번 RGB거리 C++ 풀이

3
1 100 100
100 100 100
1 100 100​

---

알고리즘 분류

• 다이나믹 프로그래밍

---

문제 설명

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

---

출력 설명

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

---

예제 입력

3
26 40 83
49 60 57
13 89 99

3
1 100 100
100 1 100
100 100 1

3
1 100 100
100 100 100
1 100 100

 

6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19

---

예제 출력

96

3

102

208

253

---

아이디어

각 색의 배열에 들어있는 값이 이전에 해당 색을 선택했을 때의 최솟값이다.

다음 단계에서 각 색의 최솟값은 색이 일치하지 않는 값 중 현재 단계에서의 최솟값을 입력받은 색의 값과 더한 값이다.

---

알고리즘

0으로 초기화된 n+1 * 3 배열 선언.

각 행의 0번째는 R, 1번째는 G, 2번째는 B 색상을 의미함.

r, g, b를 입력받음

i를 1 ~ n까지 반복문으로 하단의 내용을 반복

            arr[i][0] = min(arr[i-1][1], arr[i-1][2]) + r;
            arr[i][1] = min(arr[i-1][0], arr[i-1][2]) + g;
            arr[i][2] = min(arr[i-1][0], arr[i-1][1]) + b;

arr[n][0], arr[n][1], arr[n][2] 중 최솟값을 출력.

---

코드

#include <iostream>
using namespace std;
int main() {
    int n,r,g,b;
    cin>>n;
    int arr[n+1][3] = {0};
    for(int i=1;i<=n;i++)
        {
            cin>>r>>g>>b;
            arr[i][0] = min(arr[i-1][1], arr[i-1][2]) + r;
            arr[i][1] = min(arr[i-1][0], arr[i-1][2]) + g;
            arr[i][2] = min(arr[i-1][0], arr[i-1][1]) + b;
        }
    cout<<min(arr[n][0],min(arr[n][1],arr[n][2]));
    return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/1149

처음에는 백트래킹으로 풀다가

DP 문제임을 깨닫고 다양한 방법을 시도해 보았지만 실패했다.

이후 구글링을 통해서 해당 문제의 점화식을 알게 되었다.

그래서 코드를 수정해서 맞았다.

DP 문제는 점화식만 알면 굉장히 간단한 경향이 있다.

하지만 점화식을 유도하는 과정이 상당히 난이도가 있다.

더욱 많은 DP 문제를 풀어서 손쉽게 점화식을 생각해 내고 싶다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!