baekjoon 1149:RGB거리

baekjoon 1149 RGB거리

1149번 RGB거리

접근

대놓고 dp였다.
dp(i, k): i번째가 k로 색칠했을 때 최소 (k = 0, 1, 2)
dp(i, k) = price(i, k) + min(dp(i+1, (k+1)%3 ), dp(i+1, (k+2)%3))

코드

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

int dp(int i, int k, int n, vector<vector<int>>& price);
int cache[1000][3];
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  int n;
  for(int i = 0; i < 1000; i++){
    for(int j = 0; j < 3; j++){
      cache[i][j] = 0;
    }
  }
  cin >> n;
  vector<vector<int>> price(n, vector<int>(3));

  for(int i = 0; i < n; i++){
    cin >> price[i][0] >> price[i][1] >> price[i][2];
  }
  int ans = min(dp(0, 0, n, price), dp(0, 1, n, price));
  ans = min(ans, dp(0, 2, n, price));
  cout << ans << "\n";
  
  return 0;
}
int dp(int i, int k, int n, vector<vector<int>>& price){
  if(i == n-1){
    return price[i][k];
    
  }
  int& ret = cache[i][k];
  if(ret != 0) return ret;
  if(k == 0){
    ret = price[i][k] + min(dp(i+1, 1, n, price), dp(i+1, 2, n, price));
  }
  else if (k == 1){
    ret = price[i][k] +  min(dp(i+1, 0, n, price), dp(i+1, 2, n, price));
  }
  else if (k == 2){
    ret = price[i][k] + min(dp(i+1, 0, n, price), dp(i+1, 1, n, price));
  }
  return ret;
}

배운 점

dp쓰는 법을 제대로 처음 해본 것 같다.