#1149 RGB거리

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

1149번: RGB거리

실버 1의 문제이다. 예전에 풀었을때는 어려워서 오또케이틀린가동자 했었는데 이제는 풀었당.

#include <iostream>
#include <algorithm>
using namespace std;

int dp[1001][3];
int cost[1001][3];

int main()
{
  freopen("input.txt","r",stdin);
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    for(int j=0;j<3;j++){
      cin>>cost[i][j];
    }
  }

  dp[1][0]=cost[0][0];
  dp[1][1]=cost[0][1];
  dp[1][2]=cost[0][2];
  
  for(int i=2;i<=n;i++){
    dp[i][0]=min(dp[i-1][1],dp[i-1][2])+cost[i-1][0];
    dp[i][1]=min(dp[i-1][0],dp[i-1][2])+cost[i-1][1];
    dp[i][2]=min(dp[i-1][0],dp[i-1][1])+cost[i-1][2];
  }

  int ans[3];
  ans[0]=dp[n][0];
  ans[1]=dp[n][1];
  ans[2]=dp[n][2];
  sort(ans,ans+3);
  cout<<ans[0];
}

풀이과정은 다음과 같다.

일단 점화식을 생각하기 위해서 dp[n][빨간색] = n개의 집 중, 마지막 집을 빨간색으로 칠하는 경우의 수. 이런식으로 잡았다. 근데 빨간색을 index 로 쓸 수 없으니까 빨간색 = 0 , 초록색 = 1 , 파란색 = 2 로 했다. 결론적으로 3개의 값을 구해서 이중에 최솟값을 구하면 되는거다. 그리고 n번째 집에 칠한 색과 n-1번째 집의 색깔은 달라야 하므로, 그것도 고려해주었다.

 

dp[n][0] = min( dp[n-1][1] , dp[n-1][2] ) + 빨간색의 값 이런식이 되는 것이다.

 

이때, n=1 일때는 값이 들어가있지 않다. n이 1일 때는 그냥 해당 cost 를 넣어주면 되니까 예외 처리를 해주었다.

마지막에는 ans라는 배열에 n번째 값 3개를 넣어 오름차순으로 돌린뒤 ans[0]을 출력해주었다! 최소값이 나올테니깐 말이다.