[백준] 1149. RGB 거리

문제

https://www.acmicpc.net/problem/1149



풀이

동적 프로그래밍을 적용하여 순서대로 풀어나가면 된다.

• 가격의 총합을 저장하는 price 배열과 각 color의 가격을 저장하는 color 배열을 생성한다.
• 가장 처음인 price[0][0~2]는 color[0][0~2]까지를 저장해준다.
• 맨처음에 빨강(color[0][0])을 선택했다면 다음은 파랑(color[1][1]) 또는 초록(color[1][2])을 선택해야 한다.
• 이 규칙을 적용하여 현재 칠하고자 하는 색이 빨강이면 이전에 칠한 색 중 파랑 또는 초록 중에 가격이 더 적은 것과 더해서 값을 저장해준다. 현재 칠하고자 하는 색이 파랑과 초록인 경우도 같은 방법을 적용해준다.
• 이것을 원하는 범위까지 반복해준다.

소스 코드

//
//  RGBDistance.cpp
//  test
//
//  Created by 신기열 on 11/05/2019.
//  Copyright © 2019 신기열. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    
    int n;
    cin >> n;
    int color[n][3], price[n][3], p[1000];
    
    for(int i = 0; i < n; i++){
        cin >> color[i][0] >> color[i][1] >> color[i][2];
    }
    
    price[0][0] = color[0][0]; price[0][1] = color[0][1]; price[0][2] = color[0][2];
    price[1][0] = min(color[1][0] + color[0][1], color[1][0] + color[0][2]);
    price[1][1] = min(color[1][1] + color[0][0], color[1][1] + color[0][2]);
    price[1][2] = min(color[1][2] + color[0][0], color[1][2] + color[0][1]);
    
    p[0] = min(price[0][0], price[0][1]);
    p[0] = min(p[0], price[0][2]);
    
    p[1] = min(price[1][0], price[1][1]);
    p[1] = min(p[1], price[1][2]);
    
    for(int i = 2; i < n; i++){
        
        price[i][0] = min(color[i][0] + price[i-1][1], color[i][0] + price[i-1][2]);
        price[i][1] = min(color[i][1] + price[i-1][0], color[i][1] + price[i-1][2]);
        price[i][2] = min(color[i][2] + price[i-1][0], color[i][2] + price[i-1][1]);
        
        p[i] = min(price[i][0], price[i][1]);
        p[i] = min(p[i], price[i][2]);
    }
    
    cout << p[n-1];
    
    return 0;
}

소스코드  : https://github.com/betterafter/BaekJoon/blob/master/DP/RGBDistance.cpp