[백준/BOJ] 1149번 RGB거리 (C/C++)

백준 온라인 저지(BOJ) 1149번 RGB거리

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

1149번: RGB거리

* 사용언어 : C언어, C++

 

1. 문제

N개의 집을 R, G, B 중 하나의 색으로 칠해야 함

각각의 집을 색칠하는 비용이 주어질 때, 인접한 집의 색이 다르도록 모든 집을 칠하는 비용의 최소값을 출력

 

2. 풀이

N번 집을 Red로 색칠할 때의 총 비용은

[N번 집 Red 색칠 비용] + min([N - 1번 집 Green 색칠 총 비용], [N - 1번 집을 Blue로 색칠한 총 비용])입니다.

이 계산을 R, G, B 각각 3번 수행하면 1부터 N번 집까지 색칠할 때의 각 색깔 별 비용을 모두 구할 수 있습니다.

 

dp 수행 시 1번 집은 이전 집 색깔 제약이 없으므로 1번 집 색칠 비용을 그대로 넣고,

2부터 N까지 위와 같은 계산을 반복하면 됩니다.

 

저는 처음에 cost 배열로 입력 값을 모두 저장해둔 후 dp라는 다른 배열에 계산을 했었습니다.

하지만 생각해보니 N번을 계산할 때는 [N-1번 까지의 총 비용(dp 값)]과 [N번의 비용(cost 값)]만 있으면 되므로

이전 cost 값들을 굳이 따로 저장해둘 필요가 없다는 것을 알게 됐습니다.

(N번 계산할 때는 N번째 cost(입력)값만 보존되어 있으면 됨)

 

그래서 배열을 하나로 통일한 뒤 cost 값에 N - 1까지의 총 비용을 더해가는 방식으로 처리하였습니다.

자세한 내용은 아래 코드 참고해주시면 됩니다.

 

 

이 문제는 전형적인 dp 문제 중 하나인 '돌 놓기' 문제와 유사한 문제입니다.

구글에 '다이나믹 프로그래밍 돌 놓기' 혹은 'dynamic programming pebble placement'와 같이 검색하면

풀이가 많이 나오니 필요 시 참고하시면 됩니다.

 

단, 돌 놓기 문제는 직전에 b에 돌을 두면 양 사이드 2개를 선택할 수 있는 Pattern 4 선택지가 있습니다.

이 문제와는 다른 부분이니 학습 시 유의하시길 바랍니다.

돌 놓기 문제의 4가지 Pattern

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
1149_RGB거리
1124KB	0ms
*/
#include <cstdio>

const int CLM = 3;
int dp[1000][CLM], N;

int min(int a, int b) { return a < b ? a : b; }

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);
	for (int y = 0; y < N; ++y)
	for (int x = 0; x < CLM; ++x)
		scanf("%d", &dp[y][x]);

	for (int y = 1; y < N; ++y)
	for (int x = 0; x < CLM; ++x)
		dp[y][x] += min(dp[y - 1][(x + 1) % CLM], dp[y - 1][(x + 2) % CLM]);

	int min = dp[N - 1][0];
	if (dp[N - 1][1] < min) min = dp[N - 1][1];
	if (dp[N - 1][2] < min) min = dp[N - 1][2];
	printf("%d\n", min);
	return 0;
}