1149번 -RGB 거리

본 문제는 DP(동적계획법) 을 사용해서 풀 수 있는 가장 쉬운 문제이다.

다음 그림 과 같이 다음 칸에는 같은색을 동일하게 칠할 수 없다.

예를 들어 N 의 녹색으로 갈수 있는것은 N-1 의 빨강색과 파란색이다.

이 경우는 N의 모든색이 마찬가지 이다.

하지만 내가 구하고 싶은값의 N 까지 선택해서 왔을때 가장 최소의 비용이 드는 것이다.

따라서 N의 빨강색 은 N-1 의 초록, 파랑중 최솟값, 녹색은 N-1 의 빨강색과 파랑색 중 의

최솟값, N 의 파랑색은 N-1 의 빨강색과 초록색 중의 최솟 값과 더해진 값이 될껏이다.

이렇게해서 0 부터 ~ N 까지 했을때 N번째에는 각자 의 색마다 최소의 값을 갖는 합을

가지고 있을 것이다. 따라서 ,  N번째 중에 가장 작은 값을 출력하면 답이다.

V 배열
R	G	B
26	40	83
49	60	57
13	89	99
DP 배열
R	G	B
26	40	83
40+49	26+60	26+57
26+57+13	26+57+89	26+60+99
Ans 26+57+13

다음 과 같이 됨을 알수 있다. 아래는 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include<iostream> #include<algorithm> #include<vector> using namespace std; vector<vector<int> > V; int main(){     int N;     int M;     int A=0;     vector<vector<int> > DP;     DP.assign(1001, vector<int>(3));     cin >> N;     V.assign(N+1, vector<int>(3, 0));     for (int i = 0; i < N; i++){         generate(V[i].begin(), V[i].end(), []()->int{int a; cin >> a; return a; });     }         DP[0] = V[0];           for (int i = 1; i <= N; i++){         for (int j = 0; j < 3; j++){             DP[i][j] = min(DP[i - 1][(j + 1) % 3], DP[i - 1][(j + 2) % 3]) + V[i][j];         }     }     cout << *min_element(DP[N].begin(), DP[N].end())<<endl;           return 0; }