<Baekjoon>#1149 RGB 거리 (RGB street) c++
먼저 dp[N][3] 이렇게 만들어 줄거다. 행에는 n번째 집, 열에는 RGB의 값을 넣어준다.
dp[0][0]= 1번 집이 R를 색칠했을 경우 비용의 최솟값,
dp[0][1]= 1번 집이 G를 색칠했을 경우 비용의 최솟값,
dp[0][2]= 1번 집이 B를 색칠했을 경우 비용의 최솟값... 을 차례로 저장한다
먼저 처음 dp에 각 집을 R,G,B로 칠하는 비용을 입력받으면서 저장한다.
void input() {
cin >> N;
if (N > MAX)
exit(EXIT_FAILURE);
for (int i = 0; i < N; i++)
for (int j = 0; j < 3; j++)
cin >> dp[i][j];
}
그 다음 dp[0][i] 일 때 값들은 그대로 두고
dp[1][i]값들을 차례로 생각해본다.
dp[1][0]에는 두 번째 집이 R로 칠해졌을 경우이므로, 첫 번째 집이 R이면 안 된다. 그래서 (첫 번째 집이 G로 칠해졌을 경우 + 두 번째 집이 R로 칠해질 경우) 와 (첫 번째 집이 B로 칠해졌을 경우 + 두 번째 집이 R로 칠해질 경우)중 더 작은 값을 저장한다.
#include<iostream>
#include<algorithm>
const int MAX = 1001;
int dp[MAX][3];
int N;
using namespace std;
void input() {
cin >> N;
if (N > MAX)
exit(EXIT_FAILURE);
for (int i = 0; i < N; i++)
for (int j = 0; j < 3; j++)
cin >> dp[i][j];
}
int paintRGB() {
for (int i = 1; i < N; i++) {
dp[i][0] = min(dp[i - 1][1] + dp[i][0], dp[i - 1][2]+dp[i][0]);
dp[i][1] = min(dp[i - 1][0] + dp[i][1], dp[i - 1][2] + dp[i][1]);
dp[i][2] = min(dp[i - 1][0] + dp[i][2], dp[i - 1][1] + dp[i][2]);
}
return min({dp[N - 1][0], dp[N - 1][1], dp[N - 1][2]});
}
int main() {
input();
cout << paintRGB() << endl;
return 0;
}
Author And Source
이 문제에 관하여(<Baekjoon>#1149 RGB 거리 (RGB street) c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Baekjoon1149-RGB-거리-RGB-street-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)