코딩테스트 연습/Baekjoon
[Baekjoon] 1149번: RGB거리 / dynamic
수기
2022. 3. 31. 20:07
https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
[i+1][0]번째 줄 -> 0번째를 제외한 [i][1], [i][2]번째와의 합 중 최솟값,
[i+1][1]번째 줄 -> 1번째를 제외한 [i][0], [i][2]번째와의 합 중 최솟값,
[i+1][2]번째 줄 -> 2번째를 제외한 [i][0], [i][1]번째와의 합 중 최솟값 을 코드로 나타내면
RGB[i+1][0] = MIN(RGB[i+1][0] + RGB[i][1], RGB[i+1][0] + RGB[i][2]);
RGB[i+1][1] = MIN(RGB[i+1][1] + RGB[i][0], RGB[i+1][1] + RGB[i][2]);
RGB[i+1][2] = MIN(RGB[i+1][2] + RGB[i][0], RGB[i+1][2] + RGB[i][1]);
N-1까지 누적한 후, RGB[N-1][0], RGB[N-1][1], RGB[N-1][2] 중 최솟값이 모든 집을 칠하는 비용의 최솟값이다.
코드
//1149
#include <iostream>
#include <cmath>
using namespace std;
long long MIN(long long a,long long b){
if(a<b)return a;
else return b;
}
long long MIN3(long long a,long long b, long long c){
return ( a<c ? ( a<b ? a:b ) : ( b<c ? b:c ) );
}
int main(int argc, const char * argv[]) {
cin.tie(NULL);
ios::sync_with_stdio(0);
int N;
long long RGB[1001][3] = {0,};
cin >> N;
for(int i=0;i<N;i++) cin >> RGB[i][0] >> RGB[i][1] >> RGB[i][2];
for(int i=0;i<N-1;i++){
RGB[i+1][0] = MIN(RGB[i+1][0] + RGB[i][1], RGB[i+1][0] + RGB[i][2]);
RGB[i+1][1] = MIN(RGB[i+1][1] + RGB[i][0], RGB[i+1][1] + RGB[i][2]);
RGB[i+1][2] = MIN(RGB[i+1][2] + RGB[i][0], RGB[i+1][2] + RGB[i][1]);
}
cout << MIN3(RGB[N-1][0], RGB[N-1][1], RGB[N-1][2]);
return 0;
}