[코딩테스트 C++] RGB거리

오늘의 문제

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

RGB거리

문제 분석

• 최대 입력이 1000이므로 O(N^2) 정도의 알고리즘이면 충분하다.
• 앞의 선택이 다음에 영향을 미치므로, DP로 풀면 O(N)에 풀 수 있다. 이전까지 선택지 3가지에 대한 최선의 선택이 담겨있으며, 이번에는 그 중에서 고를 수 있는 것 중 제일 값이 덜 나가는것을 고르면 된다.

나의 풀이

#include <iostream>
using namespace std;
int n;
const int MAX = 1000;
int cost[MAX][3];

// RGB거리
int solution(){
    int color[MAX][3];
    color[0][0] = cost[0][0];
    color[0][1] = cost[0][1];
    color[0][2] = cost[0][2];
    for(int i=1;i<n;i++){
        color[i][0] = min(color[i-1][1], color[i-1][2]) + cost[i][0];
        color[i][1] = min(color[i-1][0], color[i-1][2]) + cost[i][1];
        color[i][2] = min(color[i-1][0], color[i-1][1]) + cost[i][2];
    }
    
    return min(color[n-1][0],min(color[n-1][1], color[n-1][2]));
}

다른 답안

#include <stdio.h>
#include <algorithm>
using namespace std;
int n;
int r,g,b,R,G,B,x,y,z;
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d%d",&r,&g,&b);
        if(i==0) {R=r; G=g; B=b; continue;}
        x=min(G,B)+r;
        y=min(R,B)+g;
        z=min(R,G)+b;
        R=x; G=y; B=z;
    }
    int ans=min(R,min(G,B));
    printf("%d",ans);
}

배울 점

• 백준은 입력을 처리해서그런지 입력과 동시에 문제를 푼다.