[#55][알고리즘] RGB거리 (Dynamic Programming)
백준 > RGB거리 (Dynamic Programming)
문제 링크(https://www.acmicpc.net/problem/1149)문제
RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.
각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠할 때 드는 비용의 최솟값을 출력한다.
예제 입력 1
3 26 40 83 49 60 57 13 89 99
예제 출력 1
96
C++풀이
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int test, color[1000][3], dp[1000][3];
cin >> test;
for (int i = 0; i < test; i++) {
for (int j = 0; j < 3; j++) {
cin >> color[i][j];
}
dp[0][0] = color[0][0];
dp[0][1] = color[0][1];
dp[0][2] = color[0][2];
if (i != 0) {
dp[i][0] = min(color[i][0] + dp[i - 1][1], color[i][0] + dp[i - 1][2]);
dp[i][1] = min(color[i][1] + dp[i - 1][0], color[i][1] + dp[i - 1][2]);
dp[i][2] = min(color[i][2] + dp[i - 1][1], color[i][2] + dp[i - 1][0]);
}
}
cout << min(dp[test - 1][0], min(dp[test - 1][1], dp[test - 1][2]));
return 0;
}
| cs |
- 입력 값을 color[1000][3]에 저장한 뒤, dp[0][0]~dp[0][2]에 color[0][0]~color[0][2] 각각 저장.
- i가 0이 아닐 때,
i=1일 때
dp[1][0] = min(49+40 , 49+83) = 89
dp[1][1] = min(60+26, 60+83) = 86
dp[1][2] = min(57+26, 57+40) = 83
i=2일 때
dp[2][0] = min(13+86, 13+83) = 96
dp[2][1] = min(89+89, 89+83) = 172
dp[2][2] = min(99+96, 99+172) = 185
마지막 행에서 최솟값을 가진 값 찾아 출력
=> 96
댓글
댓글 쓰기