BOJ 17404: RGB 거리 작성일 2020-02-29 https://www.acmicpc.net/problem/17404 2월동안 187문제 풀기(지난달 누적 87개) (77/187) 원형으로 된 DP, 시작지점의 state를 dp에 저장해두면 쉽게 풀 수 있다. slide window도 쓰면 좋다. 습격차 초라기에 도전해봐야겠다 이거랑 비슷해보임. 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); int N, r, g, b; cin >> N; vector<array<int,3>> arr; arr.reserve(N); for(int i = 0; i < N; i++) { cin >> r >> g >> b; arr.push_back({r,g,b}); } vector<vector<int>> dp(3, vector<int>(3)); vector<vector<int>> ndp(3, vector<int>(3)); vector<vector<int>> init(3, vector<int>(3, 1e9)); for(int j = 0; j < 3; j++) for(int k = 0; k < 3; k++) dp[j][k] = 1e9; for(int i = 0; i < 3; i++) dp[i][i] = arr[0][i]; for(int i = 1; i < N-1; i++) { ndp = init; for(int k = 0; k < 3; k++) { int o1 = (k+1) % 3; int o2 = (k+2) % 3; for(int j = 0; j < 3; j++) ndp[j][k] = min(ndp[j][k], dp[j][o1] + arr[i][k]); for(int j = 0; j < 3; j++) ndp[j][k] = min(ndp[j][k], dp[j][o2] + arr[i][k]); } dp = ndp; } int ans = 1e9; for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) for(int k = 0; k < 3; k++) { if(i == j || i == k) continue; ans = min(ans, dp[j][k] + arr[N-1][i]); } cout << ans; }