백준 온라인 저지 1149 번 RGB거리
문제
RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.
각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.
3
26 40 83
49 60 57
13 89 99
출력
첫째 줄에 모든 집을 칠할 때 드는 비용의 최솟값을 출력한다.
1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점
96
백준 온라인 저지
소스코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int arr[1001][3];
int main(){
cin >> N;
for (int i = 0; i < N; i++){
int r, g, b;
cin >> r >> g >> b;
arr[i][0] = r;
arr[i][1] = g;
arr[i][2] = b;
}
int dp[1001][3];
for (int i = 0; i < N; i++){
for (int j = 0; j < 3; j++){
if (i == 0){
dp[i][j] = arr[i][j];
}
else{
if (j == 0){
dp[i][j] = min(dp[i - 1][1], dp[i - 1][2]) + arr[i][j];
}
else if (j == 1){
dp[i][j] = min(dp[i - 1][0], dp[i - 1][2]) + arr[i][j];
}
else{
dp[i][j] = min(dp[i - 1][0], dp[i - 1][1]) + arr[i][j];
}
}
}
}
int min = dp[N - 1][0];
for (int i = 0; i < 3; i++){
if (min>dp[N - 1][i])
min = dp[N - 1][i];
}
cout << min << endl;
return 0;
}
이차원 배열로 그래프를 만들고 DP를 활용한다. 가장 윗줄부터 문제를 따라가 해당셀의 값과 전셀에서 올수 있는 가장 최소의 값을 더해 dp이차원배열을 채워나간다.
