[삼성 알고리즘] Dynamic Programming(RGB 거리)

안녕하세요! 이번에 포스팅할 내용은 동적프로그래밍 입니다.

기본적으로 동적프로그래밍을 작성하기 위한 방법은 아래 포스팅을 통해 확인하실 수 있으며 이번 포스팅에서는 백준의 RGB 문제를 통해 동적프로그래밍에 접근해보겠습니다.

 

(Dynamic Programming(2xn 타일링2)

bluemoon-1st.tistory.com/25?category=851281

1. 문제 이해

가장 최소의 비용으로 집을 모두 색칠하는 방법을 구하는 것으로 이웃한 집끼리 같은 색상을 진행할 수 없습니다.

 

2. 식 만들기

해당 문제의 경우 n 값에 따른 n번째 집이 각각 red, green, blue일 때 최솟값을 모두 가지고 있어야 합니다. 그래야 1~n번 째 까지의 모든 경우를 고려해서 전체 최소비용을 구할 수 있습니다.

 

1) n = 1

n = 1 인경우에는 red, green, blue의 최소비용은 각각 1번째 집에 색칠하는 비용 자체가 되며 이 때 red, blue, green 중 가장 최소비용이 정답이 됩니다.(하지만 해당 문제에서는 인풋이 2이상)

 

2) n >= 2

해당의 경우에는 n번째 red인경우 green인경우 blue인 경우를 고려해야 합니다. 즉

 

n이 red인경우

- n-1번째 색이 green이며 1~n-1번째 까지의 최솟값과 n이 red인 경우의 비용 합

- n-1번째 색이 blue이며 1~n-1번째 까지의 최솟값과 n이 red인 경우의 비용 합.

위 두 비용 중 최솟 값이 바로 n이 red인 경우 1~n까지의 최소비용이 될것이고.

 

마찬가지로 n이 blue, green인 경우도 위와 같은 방식으로 진행됩니다.

n이 blue인경우

- n-1번째 색이 green이며 1~n-1번째 까지의 최솟값과 n이 blue인 경우의 비용 합

- n-1번째 색이 red이며 1~n-1번째 까지의 최솟값과 n이 blue인 경우의 비용 합.

 

n이 green인경우

- n-1번째 색이 red이며 1~n-1번째 까지의 최솟값과 n이 green인 경우의 비용 합

- n-1번째 색이 blue이며 1~n-1번째 까지의 최솟값과 n이 green인 경우의 비용 합.

 

위 경우를 식으로 만들게되면.. 1~n번째 까지의 최소비용이 X(n)이라고 하고 n이 red, blue, green일 때의 최소비용을 각각 RED(n), BLUE(n), GREEN(n)이라고 한다면

RED(n) = min(Xg(n-1), Xb(n-1)) + n 번째 red비용

BLUE(n) = min(Xr(n-1), Xg(n-1)) + n 번째 blue 비용

GREEN(n) = min(Xr(n-1), Xb(n-1)) + n 번째 green 비용

이 되고 이 때, min(RED(n), GREEN(n), BLUE(n)) 의 값이 바로 X(n)이 됩니다.

 

즉 n=1부터 메모제이션 방법을 통해 n을 bottom-up 방식으로 올라가면서 n번째 값을 구함으로써 해당 동적프로그래밍 문제를 해결할 수 있습니다.

 

3. 소스 코드

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

 

int red[1001] = {0,};

int blue[1001] = {0,};

int green[1001] = {0,};

int red_price[1001]={0,};

int blue_price[1001] = {0,};

int green_price[1001] = {0,};

 

int min_price(int n) {

    if(n==1) {

        return min(red[1],min(green[1],blue[1]));

    } else {

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

            green[i]=min((red[i-1]+green_price[i]),(blue[i-1]+green_price[i]));

            blue[i]=min(red[i-1],green[i-1])+blue_price[i];

            red[i]=min(blue[i-1],green[i-1])+red_price[i];

        }

        return min(red[n],min(blue[n],green[n]));

    }

}

int main (void) {

    int n,r,g,b;

    cin>>n;

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

        cin>>r>>g>>b;

        red_price[i]=r;

        green_price[i]=g;

        blue_price[i]=b;

    }

    red[1]=red_price[1];

    green[1]=green_price[1];

    blue[1]=blue_price[1];

 

    cout<<min_price(n);

    return 0;

}