[BOJ, C++]#1149_RGB거리, DP

#1. 문제

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

 

---

 

#2. 풀이

 

1. DP

[알고리즘]#5_동적 계획법

동적 프로그래밍은 문제에 주어진 입력 크기에 따라 중복되는 하위 문제를 재귀적으로 해결하고, 이 결과 값들을 기억하는 것으로 중복 계산을 피해 최적화를 수행하고 효율적으로 최적해를 찾아냅니다. 

 

2. 현재 문제에 대한 세 가지 경우!

1. 먼저, 현재 집에 대하여 3가지 경우에 대한 최소 비용을 각각 기억해 줍니다. 이를 위해, 2차원 컨테이너를 통해 빨간색을 칠했을 경우, 초록색을 칠했을 경우, 그리고 파란색을 칠했을 경우를 모두 저장합니다.
2. 현재 집이 "R"일 경우, 이전 집의 "G"와 "B"의 비용 중 더 작은 비용을 현재 집의 "R"경우에 더해줍니다.
3. 최종적으로, N번째 집의 R, G, 그리고 B 경우의 비용 중 최소 비용을 결과로 출력해 줍니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/1149
*   @문제: 1~N번 집을 몇 가지 조건을 준하며 빨강, 초록, 파랑으로 칠하는 최소 비용

        1. DP[i] != DP[i-1] && DP[i] != DP[i+1]
        2. DP[i] != DP[i+1], if i = 2
        3. DP[i] != DP[i-1], if i = N

*   @설명
        1. 2차원 vector 컨테이너, vector<vector<int>> dp(2, vector<int>(3,0)) 사이즈 선언
        2. 현재 집에 대하여 빨간색 칠할 경우 이전 집의 초록색 칠할 경우와 파란색 칠할 경우 중 최소 비용을 더해준다.
*/


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N;

    cin >> N;

    vector<vector<int>> dp(2, vector<int>(3, 0));
    for(int i=0; i<N; ++i)
    {   
        int r, g, b;
        cin >> r >> g >> b;

        int current = i%2;
        int prev = (i-1+2)%2;

        dp[current][0] = min(dp[prev][1], dp[prev][2]) + r;
        dp[current][1] = min(dp[prev][0], dp[prev][2]) + g;
        dp[current][2] = min(dp[prev][0], dp[prev][1]) + b;
    }

    cout << min(dp[(N-1)%2][0], min(dp[(N-1)%2][1], dp[(N-1)%2][2]));

    return 0;
}

 

---