백준 17404 c++ "RGB거리 2" -PlusU|ltraCode-

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

 

[필자 사고]

재미난 문제이다. 동적프로그래밍을 이용하여 최소값을 찾아야 된다.

필자는 최소값을 찾기 전에 미리 사전에 first형태로 특정 인덱스를 선택했다고 가정하는식으로 문제를 해결했다.

예를들어 R을 선택했다고 한다면 R에 값만 기본적인 값을 넣고 나머지 G와 B인덱스 초기에는 큰값을 넣어 해당 인덱스가 선택되지 않게 유도했따.
마지막 점검때 R인덱스가 아닌 G와 B인덱스중 작은값을 선택하여 문제를 해결하는 방식으로 해결했다.

 

아래는 자세한 코드해설이다.

[코드 해설]

1. 입력 처리 (Input 함수)

• N : 집의 개수를 입력받는다.
• arr[i][k] : i번째 집을 k(1=빨강, 2=초록, 3=파랑) 색으로 칠하는 비용을 저장한다.
• dp[i][k] : i번째 집까지 칠했을 때, k 색으로 칠한 경우의 최소 비용을 저장하는 DP 테이블.

입력받은 값을 arr 벡터에 저장하고, DP 배열도 같은 크기로 초기화한다.

---

2. DP를 이용한 최소 비용 계산 (Game_Start 함수)

(1) 첫 번째 집을 고정하는 반복문

• 첫 번째 집을 각각 빨강(1), 초록(2), 파랑(3)으로 칠하는 경우를 따로 계산한다.
• 첫 번째 집을 선택한 후, 나머지 두 색의 비용은 99999999로 설정하여 선택되지 않도록 한다.

(2) DP 배열 채우기

• dp[i][1] = arr[i][1] + min(dp[i-1][2], dp[i-1][3])
• dp[i][2] = arr[i][2] + min(dp[i-1][1], dp[i-1][3])
• dp[i][3] = arr[i][3] + min(dp[i-1][1], dp[i-1][2])

즉, 현재 집을 k색으로 칠할 때, 이전 집을 k가 아닌 다른 두 색 중 비용이 작은 것을 선택하여 누적한다.

(3) 마지막 집에서 최소 비용 선택

• 첫 번째 집과 같은 색이 아닌 경우만 고려하여 최소 비용을 갱신한다.

---

3. 결과 출력

• 세 가지 경우 중 가장 작은 resultCount 값을 출력하여, 모든 조건을 만족하면서 칠하는 최소 비용을 구한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int N;
vector<vector<int>> dp;
vector<vector<int>> arr;

void Input() {
	cin >> N;
	arr.assign(N + 1, vector<int>(4));
	dp = arr;

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

void Game_Start() {
	int resultCount = 1e9;
	for (int first = 1; first <= 3; first++) {
		for (int i = 1; i <= 3; i++) {
			if (i == first) {
				dp[1][i] = arr[1][i];
			}
			else {
				dp[1][i] = 99999999;
			}
		}

		for (int i = 2; i <= N; i++) {
			dp[i][1] = arr[i][1] +min(dp[i - 1][2], dp[i - 1][3]);
			dp[i][2] = arr[i][2] +min(dp[i - 1][1], dp[i - 1][3]);
			dp[i][3] = arr[i][3] +min(dp[i - 1][1], dp[i - 1][2]);
		}

		for (int i = 1; i <= 3; i++) {
			if (first != i) {
				resultCount = min(resultCount, dp[N][i]);
			}
		}
	}
	cout << resultCount;
}

int main(void) {
	Input();
	Game_Start();
}