[백준] 17404-RGB거리 2(C++)

문제링크:www.acmicpc.net/problem/17404

17404번: RGB거리 2

 

전형적인 dp문제입니다.

 

근데 문제조건처럼 1과 n이 연결되어 있다는 것을 인지해야합니다.

 

구현방법은 간단합니다.

 

첫번째의 시작점을 정해두고 dp를 구하면 됩니다. 이렇게 3번 반복하며 시작점과 끝점의 값이 다르도록 구현하는 것이 핵심입니다.

 

위 설명과 아래 주석을 함께 보시면 이해하는데 어려움 없을 겁니다!

아래는 정답코드입니다.

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


int n = 0, result = 1000000000;
int arr[1001][3] = { 0, };
int dp[1001][3] = { 0, };

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++)
		for(int j=0;j<3;j++)
			cin >> arr[i][j];

	for (int k = 0; k < 3; k++) {

		//1. 초기값 설정
		for (int i = 0; i < 3; i++)
			dp[1][i] = 1000000000;
		dp[1][k] = arr[1][k];

		
		//2. 이후 계산
		for (int i = 2; i <= n; i++) {
			dp[i][0] = arr[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
			dp[i][1] = arr[i][1] + min(dp[i - 1][2], dp[i - 1][0]);
			dp[i][2] = arr[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
		}

		//3. 초기값이 아닌 경우에만 result 도출
		for (int i = 0; i < 3; i++) {
			if (k == i) continue;
			result = min(result, dp[n][i]);
		}
	}

	cout << result << endl;
	return 0;
}