[BOJ][C++] 백준 1149번 RGB 거리
Updated:
1149번 RGB 거리
1. 문제 정보
백준 온라인 저지 [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보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
예제 입력1
3
26 40 83
49 60 57
13 89 99
예제 출력1
96
시간 / 메모리 제한
0.5초 / 128MB
2. 생각
-
i번째 집의 색을 칠할 때 i-1번째 집과 i+1번째 집과 겹치지 않도록 칠하는 방법을 구할 것입니다. n개의 집, n-1개의 집, … , 2개의 집을 색칠하는데 드는 최소의 비용을 구하는 것 처럼 큰 문제를 작은 문제로 쪼갤 수 있고, 작은 문제들의 합을 통해 큰 문제의 답을 찾을 수 있으므로 다이나믹 프로그래밍 방법으로 풀겠습니다.
-
dp[n]을 n개의 집을 주어진 조건에 맞추어 RGB로 색을 칠하는데 드는 최소의 비용으로 정의하고 dp[n][1]은 n번째 집을 빨강으로, dp[n][2]를 n번째 집을 초록으로, dp[n][3]을 n번째 집을 파랑으로 칠하는데 드는 최소의 비용으로 정의하겠습니다.
- 현재 n번째에 빨강으로 칠하려고 할 때 이전에 빨강으로 칠하면 안되므로 n-1번째는 초록이나 파랑으로 칠했어야합니다. 따라서 n번째 집을 빨강으로 칠하는 비용에 n-1번째 집을 초록이나 파랑으로 칠하는 비용 중 작은 값을 더해야합니다.
- dp[n][1] = min(dp[n-1][2], dp[n-1][3])
- 초록과 파랑으로 칠할 때도 3번과 같이 확장을 하면 최종적으로 아래와 같은 점화식을 도출할 수 있습니다.
- dp[i][1] = min(dp[i-1][2], dp[i-1][3])
- dp[i][2] = min(dp[i-1][1], dp[i-1][3])
- dp[i][3] = min(dp[i-1][1], dp[i-1][2])
-
그리고 최종적으로는 dp[n][1], dp[n][2], dp[n][3] 중 가장 작은 값이 문제의 조건에 맞추어 n개의 집을 RGB 색으로 칠하는 최소의 비용입니다.
- 최소를 구하는 방법으로는
헤더의 min 함수를 사용했습니다.
- plus 참고
| 빨강 | 초록 | 파랑 | |
|---|---|---|---|
| 1 | 26 | 40 | 83 |
| 2 | 49 + 40 = 89 | 60 + 26 = 86 | 57 + 26 = 83 |
| 49 + 83 = 132 | 60 + 83 = 143 | 57 + 40 = 97 | |
| 3 | 13 + 86 = 99 | 89 + 89 = 178 | 99 + 89 = 188 |
| 13 + 83 = 96 | 89 + 83 = 172 | 99 + 86 = 185 |
-> 연한 회색 : 어떤 색과 합쳐야 하는지.(ex : 빨+초 or 빨+파)
-> 진한 회색 : n번째에 해당하는 해답.
3. 소스코드 (C++)
