[C++] 백준 1149번 : RGB거리 (S1)

#문제

www.acmicpc.net/problem/1149

1149번: RGB거리

 

#풀이 & 학습한 내용

각각의 집에 대해 빨강, 초록, 파랑으로 칠했을 때의 Optimization(이 문제에선 비용의 최솟값)을 따로 살펴본다. 그리고 dp[i][0]을 "i번째 집을 빨강으로 칠했을 때의 첫번째 집부터 i번째 집까지의 비용합의 최솟값"으로 정의한다. dp[i][1], dp[i][2]는 앞의 정의에서 빨강을 초록, 파랑으로 바꾸어 생각한다. 아래 코드의 18~20행에 해당하는 optimal substructure를 통해 for문으로 dp배열을 1부터 N까지 채워나간다. 그리고 정답은 dp[N][0], dp[N][1], dp[N][2] 중에 최솟값이다. 

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int p[1002][3];
int dp[1002][3];
 
int main(void) {
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> p[i][0] >> p[i][1] >> p[i][2];
    }
 
    dp[1][0] = p[1][0]; dp[1][1] = p[1][1]; dp[1][2] = p[1][2];
    for (int i = 2; i <= N; i++) {
        dp[i][0] = min({ dp[i - 1][1] , dp[i - 1][2] }) + p[i][0];
        dp[i][1] = min({ dp[i - 1][0] , dp[i - 1][2] }) + p[i][1];
        dp[i][2] = min({ dp[i - 1][0] , dp[i - 1][1] }) + p[i][2];
    }
 
    cout << min({dp[N][0], dp[N][1], dp[N][2]}) << '\n';
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Dynamic_Programming/BOJ_1149.cpp

HoYoungChun/BOJ_algorithm