[백준 - 1149] RGB거리

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
using namespace std;

#define MIN(x,y) ((x) < (y) ? x : y)

#define MAX 1001
#define R 0
#define G 1
#define B 2

int DP[MAX][3];
int arr[MAX][3];

int main()
{
	//1. Get input
	ios::sync_with_stdio(0), cin.tie(0);

	int N; cin >> N;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			cin >> arr[i][j];
		}
	}

	//2. Set inital value
	DP[1][R] += MIN(arr[0][G],arr[0][B]) + arr[1][R];
	DP[1][G] += MIN(arr[0][R],arr[0][B]) + arr[1][G];
	DP[1][B] += MIN(arr[0][R],arr[0][G]) + arr[1][B];


	//3. Loop
	for (int i = 2; i < N; ++i)
	{
		DP[i][R] += MIN(DP[i - 1][G],DP[i - 1][B]) + arr[i][R];
		DP[i][G] += MIN(DP[i - 1][R],DP[i - 1][B]) + arr[i][G];
		DP[i][B] += MIN(DP[i - 1][R],DP[i - 1][G]) + arr[i][B];
	}

	//4. Print
	cout << MIN(MIN(DP[N - 1][R],DP[N - 1][G]),DP[N - 1][B]);
	return 0;
}

---

||사고 과정

약 50분 정도 걸리긴 했지만 나의 힘으로 한번에 풀어서 넘 기쁘당ㅠ

암튼 이번에는 막무가내로 설계하지 않고

테이블을 만들고, 초기 값을 넣고, 점화식을 작성해보려 노력했다.

 

전에 문제로 생각한 DP란 좀 똑똑한 브루트 포스라고 생각했기 때문에

마지막집이 R일때 ,B일때, G일때 최소값을 다 구하면 될것이라고 생각을 했다.

 

그렇게 초기 값을 넣는 과정에서 좀 구체적으로 풀이를 파악할 수 있었다.

---

||사용 기법

• DP1

---

||풀면서 느낀 것

• 테이블, 초기값, 점화식을 꼭 생각하자

꼭