[동적프로그래밍] 백준 1149번 RGB거리(C++)

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

 

rgb 거리는, 맞닿아 있는 번호의 집들은 같은 색이 되면 안된다는 심플한 문제이다.

 

예를들어

3번째의 집은 2번째 집의 색깔과 겹치면 안되고 4번째 집은 3번째 집의 색깔과 겹치면 안된다.

그 색깔은 rgb니까 세개의 경우의 수 만을 가지고 문제를 풀면 될 것 같다.

 

예를들어 i번째 집에서 색깔을 구할 때 r,g,b의 경우를 모두 미리 생각 후, 직전 번호들의 집에서 색깔만 다르게 가져오면 되지 않을까?

0 = r

1 = g

2 = b

인 경우

 

home[i][0] +=home[i-1][1] or home[i-1][2] 이렇게 말이다

코드를 한번 짜보자

 

#include <iostream>

#include <cmath>

#include <algorithm>

int dp[1001][3];

using namespace std;

int main()

{

    int n;

    cin >> n;

    for (int i = 1; i <= n; i++)

    {

        cin >> dp[i][0] >> dp[i][1] >> dp[i][2];

    }

    for (i = 2; i <= n; i++)

    {

        dp[i][0] += min(dp[i - 1][1], dp[i - 1][2]);

        dp[i][1] += min(dp[i - 1][0], dp[i - 1][2]);

        dp[i][2] += min(dp[i - 1][1], dp[i - 1][0]);

    }

    int tempmin;

    tempmin = min(dp[n][0], dp[n][1]);

    tempmin = min(tempmin, dp[n][2]);

    cout << tempmin;

}

 

끝