[동적프로그래밍] 백준 17404번 rgb 거리 2(C++)

해당 문제는 rgb 거리 1 문제에서 파생된 문제로

https://lee-soo.tistory.com/3

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

해당 포스터는 여기있다.

 

정말 단순히, 기존 문제에서 1번집과 n번집의 색깔이 같으면 안된다는 결론에 다다른다.

이러한 dp문제들의 경우 저번 문제에서 했던 코드를 가져와서 각자 rgb의 최소의 값을 가져올 때 값을 하나 고정해놓으면 좋다.

 

1번집의 색깔을 미리 고정시켜 놓는 것이다.

그 후

나머지의 값은 dp를 통해 정하고

마지막 n 값이 되었을 때는, 1번집의 색깔을 제외한 다른 색깔을 선택한 경우의 수만 비교를 하는 것이다.

 

#include <iostream>

#include <cmath>

#include <algorithm>

int dp[1001][3];

using namespace std;

int main()

{

    int n;

    cin >> n;

    int arr[1001][3];

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

    {

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

    }

    int tempmin = 999999;

    for (int count = 0; count <= 2; count++)

    {

        for (int i = 0; i < 3; i++)

            dp[1][i] = (i == count) ? arr[1][i] : 9999999;

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

        {

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

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

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

        }

        for (int i = 0; i <= 2; i++)

        {

            if (i == count)

                continue;

            else

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

        }

    }

    cout << tempmin;

}

 

 

해당 코드에서 보시다 시피 처음 for문에서 돌리는 값은 바로 rgb의 색깔을 정한 값이다 ( 0일때는 r ,1일때는 g, 2일때는 b )

arr[1][i]를 큰 값으로 해놓는 이유는 차후 arr[1][i]번째는 사용하지 않은데 dp가 거듭되다 보면 중간에 사용하지 않는 값들이 들어갈 때 min을 통해 자동으로 걸러지게 해놓기 위해서이다.

이후 for문 내부에는 for문을 하나 더 사용하여 현재 사용한 1번째 집의 색깔을 걸러준다(continue) 그 후 나머지 색깔들에 대해 min을통해 최솟값을 계속 찾아주게 되는것을 반복하면 된다.