[백준/C++] RGB거리 2 (No. 17404)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 N번째 집이 N-1번째 집과 N+1번째 집의 색과 다르게 색칠하는 경우 최소의 비용을 구하는 문제다.

 

단, 1번 집과 N번째 집도 서로 색이 달라야 한다. 

즉, 처음과 끝이 연결된 원탁과 같은 경우다.

 

하지만 처음과 끝이 연결됐다고 해서 크게 어려운 문제는 아니다.

처음과 끝의 경우를 고려해 탐색하면 쉽게 풀 수 있는 문제다.

 

i번째 집을 색칠하기 위해서는 마지막에 색칠된 i-1번째 집과 i번째 집의 색이 다르면 된다.

그러므로 i번째 집을 R로 색칠하기 위해서는 i-1번째 집을 G, B로 색칠하는 경우만 고려하면 된다.

 

그리고 처음에 색칠하는 집의 경우를 기억해야 마지막에 어떤 집을 색칠하는게 최선인지 고려할 수 있기 때문에 다음과 같은 3차원의 DP배열을 만든다.

 

DP = [첫번째 집의 색][i번쨰 집의 색][i 번째]

 

그러면 DP [첫번째 집의 색][i번쨰 집의 색][i 번째]의 값은

 

DP [첫번째 집의 색][i번쨰 집의 색과 다른 j색][i-1 번째] + RGB[ [i번쨰 집의 색과 다른 j색 ][i번째 집을 색칠하는 비용]

중 최소값으로 나타낼 수 있다.

 

이렇게 이전 집까지 색칠하는데 드는 최소 비용을 이용해 현재 집까지 색칠하는 최소비용을 구해서 문제를 해결할 수 있다.

 

 

​

[아이디어 정리]

1. 처음 색칠하는 집과 마지막에 색칠하는 집의 색이 달라야 하므로 처음에 어떤 집을 색칠했는지 저장하도록 DP베열을 [첫번째 집의 색][i번쨰 집의 색][i 번째]를 저장하는 3차원 DP배열로 만든다.
2. 현재 색칠해야하는 집의 색과 이전에 색칠하는 집의 색이 달라야 하므로 이를 고려해 이전의 최소비용을 이용해 현재 집의 최소 비용을 구한다.
3. 최종적으로 첫번쨰 집과 N-1번째 집의 색과 다르게 N번째 집을 색칠하고 이 경우들의 최소비용을 계산해 출력한다.

 

 

 

Code

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 2087654321;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int N;
	cin >> N;
	vector<vector<int>> RGB(3,vector<int>(N));
	for (int j = 0; j < N; j++){
		for (int i = 0; i < 3; i++) 
		{
			cin >> RGB[i][j];
		}
	}
	vector<vector<vector<int>>>DP(3,vector<vector<int>>(3, vector<int>(N,INF))); //시작이 [시작][마지막][n-1번째]
	DP[0][0][0] = RGB[0][0], DP[1][1][0] = RGB[1][0], DP[2][2][0] = RGB[2][0];
	for (int i = 1; i < N - 1; i++) {
		for (int st = 0; st < 3; st++) {
			for (int j = 0; j < 3; j++) {
				for (int k = 0; k < 3; k++) {
					if (j != k)
					{
						DP[st][j][i] = min(DP[st][k][i-1] + RGB[j][i], DP[st][j][i]);
					}
				}
			}
		}
	}
	int minAns = INF;
	for (int st = 0; st < 3; st++)
	{
		for (int ed = 0; ed < 3; ed++) {
			for (int i = 0; i < 3; i++) {
				if (i != ed && i != st) {
					minAns = min(minAns,DP[st][ed][N - 2]+RGB[i][N-1]);
				}
			}
		}
	}
	cout << minAns;
	return 0;
}

 

---

처음에는 마지막 집의 색만 기억하도록 코드를 구현하고 있었는데, 그러면 처음에 어떤 색으로 색을 칠했는지 알 수 없어서 처음 집의 색도 기록하는 DP배열을 만들어 해결했다.

문제에 대한 예외가 빠르게 생각나서 쉽게 풀 수 있었던 것 같다.

 

https://www.acmicpc.net/problem/17404