[C] 1149: RGB거리

전형적인 Dynamic Programming 문제인걸 알 수 있었는데 그 이유는

subproblem을 여러번 이용해야하기 때문에 이를 위해서 dp[]에 저장해서 이용해야했고

최솟값과 관련된 문제였기 때문이다.

 

이 문제는 i=1일때부터 하나하나씩 해보면 점화식을 구하는 것보다는

i=n일때부터 거꾸로 생각하는게 좀 더 떠올리는게 쉬웠던 것 같다. (2Xn 타일링2와 같이!)

그리고 빨강,초록,파랑 각각을 선택했을때 최선인 경우를 따로따로 저장하는 것이

각각 생각하지 않고  dp[i]일때 최선인 것을 저장하는 것보다 효율적이었는데

이는 똑같은 색깔을 두번 연속 선택하지 못한다면 그 다음에 최선인 경우를 빨리 찾기 위해서이다.

 

#include <stdio.h>

int red[1001];
int green[1001];
int blue[1001];
int dp[1001][3];

  int main(void)
  {
     int n;
    scanf("%d",&n);

    for(int i=1;i<=n;i++)
      {
        scanf("%d %d %d",&red[i],&green[i],&blue[i]);
      }
    dp[1][0]=red[1];
    dp[1][1]=green[1];
    dp[1][2]=blue[1];
    for(int i=2;i<=n;i++)
      {
        dp[i][0]=dp[i-1][1]<dp[i-1][2]? dp[i-1][1]+red[i]:dp[i-1][2]+red[i];
        dp[i][1]=dp[i-1][0]<dp[i-1][2]? dp[i-1][0]+green[i]:dp[i-1][2]+green[i];
        dp[i][2]=dp[i-1][0]<dp[i-1][1]? dp[i-1][0]+blue[i]:dp[i-1][1]+blue[i];
       // printf("%d %d %d\n",dp[i][0],dp[i][1],dp[i][2]);
      }
    

    int min=dp[n][0]<dp[n][1]?dp[n][0]:dp[n][1];
    min=min<dp[n][2]?min:dp[n][2];

    printf("%d",min);
      
  }