(ALGO) 백준 1149번 문제 - RGB거리

08 Jul 2017

Reading time ~1 minute

1149

이 문제의 접근 방식은, 먼저 모든 경우의 수를 다 구해서 최소 값을 구하게 한 다음,
중복 연산하는 부분을 DP를 이용해 제거했다.

#include <iostream>

using namespace std;

int cost[3][1001]; //input
int d[3][1001] = {0,}; //memorize

int N;

int getMinCost(int color_index,int home_index)
{
    if(home_index >= N)
        return 0;

    if(d[color_index][home_index] != 0)
        return d[color_index][home_index];

    int m = -1;

    for(int i=0;i<3;i++)
        if(i != color_index)
        {
            if( m == -1 )
                m = cost[color_index][home_index] + getMinCost(i, home_index + 1);
            else
                m = min(m, cost[color_index][home_index] + getMinCost(i, home_index + 1));
        }

    d[color_index][home_index] = m;
    return m;
}
int main()
{
    cin>>N;

    for(int i=0;i<N;i++)
        cin>>cost[0][i]>>cost[1][i]>>cost[2][i];

    int m = -1;

    for(int i=0;i<3;i++)
        if(m == -1)
            m = getMinCost(i, 0);
        else
            m = min(m, getMinCost(i, 0));

    cout<<m<<endl;

    return 0;
}

정답 처리는 되었지만, DP를 사용하지 않고 깔끔한 방법이 있었다.

#include <stdio.h>
#include <algorithm>
using namespace std;

int main(void) {
	int n, r, g, b, x, y, z;;
	scanf("%d", &n);

	while(n--){
		scanf("%d %d %d", &r, &g, &b);
		r += min(y, z);
		g += min(x, z);
		b += min(x, y);
		x = r, y = g, z = b;
	}
	int m = min(x, y);
	printf("%d", min(m, z));
}

algorithm