이번 문제는 백준 1149번 RGB거리 코드 라는 문제 입니다.
문제 링크 : https://www.acmicpc.net/problem/1149
dp 를 이용하는 가장 기초적이고 또렷한 문제 입니다.
풀이
빨간색 -> 녹색 , 파란색
녹색 -> 빨간색, 파란색
파란색 -> 빨간색, 녹색
라고 생각하고 푸시면 간단합니다! .
다만 위의 역방향으로 생각을 해주시면 됩니다.
빨간색은 그 전이 파란색, 녹색 일 때만 쓸 수 있습니다.
그렇다면 당연히 빨간색 칸 전에 는 녹색, 파란색 중 누적 비용이 제일 적은 것을 선택 하시면 되는 겁니다 .
최소값 비교는 기본 라이브러리를 사용 해도 좋지만
저는
int min(int a, int b) {
return a < b ? a : b;
}
int min(int a, int b, int c) {
a = min(a, b);
return min(a, c);
}
위와 같이 마지막 최소값도 찾기 위해, min 이라는 함수를 만들어서
오버로딩 하여 사용 하였습니다.
코드
#include <iostream>
#include <vector>
#include <stdio.h>
#include <cmath>
using namespace std;
int min(int a, int b) {
return a < b ? a : b;
}
int min(int a, int b, int c) {
a = min(a, b);
return min(a, c);
}
int main() {
int n;
cin >> n;
vector<vector<int>> cost(n, vector<int>(3));
vector<vector<int>> dp(n, vector<int>(3));
for (int i = 0; i < n; i++) {
cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
}
dp[0][0] = cost[0][0];
dp[0][1] = cost[0][1];
dp[0][2] = cost[0][2];
for (int i = 1; i < n; i++) {
dp[i][0] = cost[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
dp[i][1] = cost[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
dp[i][2] = cost[i][2] + min(dp[i - 1][1], dp[i - 1][0]);
}
cout << min(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]);
return 0;
}