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

문제 링크입니다 https://www.acmicpc.net/problem/17404

17404번: RGB거리 2

DP문제였습니다.

문제 조건

출력 예시(40 + 57 + 13)

 

"RGB 거리1" 과는 다르게 N번과 1번의 색깔이 달라야한다는 조건이 추가되었습니다.

따라서 1번 집에 R,G,B를 선택했을때를 전부 확인한뒤, 최솟값을 비교해주면 됩니다!

 

문제 접근 방법

1. 1번 집의 R,G,B를 순서대로 선택한다.

2. R을 선택했을때 -> 2번 집의 G,B만 값을 구하고, R의 값에는 매우 큰 값을 넣는다.

3. 3번~N번 집까지는 R,G,B 선택에 따라서 작은 값을 선택한다.

4. N번과 1번집의 색이 다를 경우에만 최솟값을 구한다.

5. 위 과정을 R,G,B를 반복한다.

 

예를 들어 1번 집에 R을 선택했다고 가정하겠습니다.

그렇다면 2번 집은 R을 선택하지 못합니다. -> 3번~N번 집까지도 R을 선택하지 못한다는 뜻입니다. 따라서 2번집의 R 값에는 매우 큰 값을 넣어서 선택을 아예 못하도록 합니다.

나머지 2번 집의 G,B는 1번 집의 R값을 더해줍니다. 

3번부터 ~ N번집까지 R,G,B 색에 따라서 값을 구해줍니다.

 

마지막으로는 N번집과 1번 집의 색이 다를 경우에만 최솟값을 구해줍니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int N;
int map[1001][4];
int dp[1001][4];
int maxi = 10000001;

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= 3; j++) {
			cin >> map[i][j];
		}
	}
	for (int k = 1; k <= 3; k++) {
		for (int i = 1; i <= 3; i++) {
			dp[1][i] = map[1][i];
		}
		for (int i = 1; i <= 3; i++) {
			if (k == i) dp[2][i] = 1000001;
			else dp[2][i] = dp[1][k] + map[2][i];
		}
		for (int i = 3; i <= N; i++) {
			for (int j = 1; j <= 3; j++) {
				if (j == 1) {
					dp[i][j] = min(dp[i - 1][2], dp[i - 1][3]) + map[i][j];
				}
				if (j == 2) {
					dp[i][j] = min(dp[i - 1][1], dp[i - 1][3]) + map[i][j];
				}
				if (j == 3) {
					dp[i][j] = min(dp[i - 1][2], dp[i - 1][1]) + map[i][j];
				}
			}
		}
		for (int i = 1; i <= 3; i++) {
			if (k != i) {
				maxi = min(maxi, dp[N][i]);
			}
		}
		memset(dp, 0, sizeof(dp));
	}
	cout << maxi;
	return 0;
}

 

 

 

 

질문 및 조언은 댓글 남겨주세요!