[백준]1149번: RGB거리

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

1149번: RGB거리

---

오랜만에 dp 문제!

문제 풀면서 dp라는건 알았지만,,, 자꾸 안 풀려서 다른 분들 풀이를 참고했다.

난 왜 이렇게 어렵지 ㅠㅠㅠ

 

풀이

✅ dp 배열에  i번째 집이 빨간색인경우, 초록색인 경우, 파란색인 경우의 최소 누적 비용을 저장한다.

 

🐥 i번째 집이 빨간색인 경우

 최소 누적 비용 = (i번째 집을 빨강으로 칠하는 데 드는 비용 ) + min( i-1번째 집이 초록색인 경우의 최소 누적 비용 , i-1번째 집이 파란색인 경우의 최소 누적 비용)

 

🐥 i번째 집이 초록색인 경우

 최소 누적 비용 = (i번째 집을 초록으로 칠하는 데 드는 비용 ) + min( i-1번째 집이 빨강색인 경우의 최소 누적 비용 , i-1번째 집이 파란색인 경우의 최소 누적 비용)

 

🐥 i번째 집이 파란색인 경우

 최소 누적 비용 = (i번째 집을 파랑으로 칠하는 데 드는 비용 ) + min( i-1번째 집이 빨강색인 경우의 최소 누적 비용 , i-1번째 집이 초록색인 경우의 최소 누적 비용)

 

✅ 이렇게 쭉쭉 저장한 뒤, n번째 집이 빨간색, 초록색, 파란색인 경우의 최소 비용을 출력한다.

 

 

제출 코드 c++

#include <iostream>

using namespace std;

int dp[3][1000];
int cost[3][1000];

int main(){

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

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

  return 0;
}