백준 알고리즘 1149 (RGB거리) - C++, Python

[문제] 백준 알고리즘 1149 (RGB거리)

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

1149번: RGB거리

집에 빨강, 초록, 파랑 중에 하나의 색을 칠하려는데, 이웃은 같은 색을 칠할 수 없다.

각 색깔에 대한 비용이 주어질 때, 모든 집을 칠하는 최소값을 구하는 문제이다.

집의 갯수 n이 주어지고, DP 문제이므로 점화식을 구해야한다.

단계별로 풀어보기로 들어가보면, 힌트 "부분문제를 정의해봅시다."라고 적혀있다.

 

부분문제를 해결하고 나서 큰 문제를 해결하는 분할정복 비슷한 느낌이다.

먼저, 일반적인 점화식을 구하기 위해서는 [i-1], [i], [i+1]의 형식으로 생각하는 것이 도움이 된다.

 

가장 작은 부분문제라고 생각한다면, 2개의 집을 칠하는 문제로 생각할 수 있다.

배열 dp[i]이 R이라 가정하면, dp[i-1]와 이웃이므로 G 또는 B만 올 수 있다.

여기서, G 또는 B 중에 최소값을 구하기 위해서는, G나 B 중에 그냥 작은 값을 찾으면 된다(!)

dp[i]이 B라면 dp[i-1]은 R 또는 G 중에 작은 값, dp[i]이 G라면 dp[i-1]은 R 또는 B 중에 작은 값이다.

이렇게 부분문제는 해결되었다.

 

이걸 큰 문제로 생각한다면, 모든 여러 개의 집을 칠하는 문제가 되므로

색깔 별로 부분문제를 누적하며 해결하는 방식이 좋을 것 같다.

따라서 배열 dp[i][0]는 R, dp[i][1]는 G, dp[i][2]는 B를 칠하는 부분문제이다.

누적시켜 마지막 dp[n-1][0] , dp[n-1][1], dp[n-1][2] 중에 최소값을 찾으면 된다.

 

[문제 해결]

1. n 입력, 색깔별 비용 cost[1001][3], 누적 값 dp[1001][3] 선언 (배열 크기 : [n+1][3색])

2. 점화식은 dp[i][색깔] = cost[i][색깔] + min(dp[i-1][안 쓴 색깔], dp[i-1][남은 색깔])과 같이 나타낼 수 있다.

    - i=0에서 [i-1]은 성립하지 않으므로, 초기 비용을 i=0일 때 대입해준다.

    - for문 안에 3색의 점화식을 적고 i=1부터 n-1까지 반복한다. 

3. dp[n-1][0] , dp[n-1][1], dp[n-1][2] 중에 최소값을 찾으면 완료

 

[C++]

#include <cstdio>
using namespace std;

int n, cost[1001][3], dp[1001][3]; // [n][color]

int min(int a, int b) {
	if (a > b) return b;
	else return a;
}

int RGB() {
	// i = 0, R or G or B 
	dp[0][0] = cost[0][0]; // start R
	dp[0][1] = cost[0][1]; // start G
	dp[0][2] = cost[0][2]; // start B
	for (int i = 1; i < n; i++) {
		dp[i][0] = cost[i][0] + min(dp[i - 1][1], dp[i - 1][2]); // now R + before G or B
		dp[i][1] = cost[i][1] + min(dp[i - 1][0], dp[i - 1][2]); // now G + before R or B
		dp[i][2] = cost[i][2] + min(dp[i - 1][0], dp[i - 1][1]); // now B + before R or G
	}
	return min(min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		// 0, 1, 2 = R, G, B
		scanf("%d %d %d", &cost[i][0], &cost[i][1], &cost[i][2]);
	}
	printf("%d", RGB());
	return 0;
}

 

[Python]

import sys
input = sys.stdin.readline
n = int(input())
cost = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * 3 for _ in range(n)]

def init():
    dp[0][0] = cost[0][0]
    dp[0][1] = cost[0][1]
    dp[0][2] = cost[0][2]
    return

def RGB():
    for i in range(1, n):
        dp[i][0] = cost[i][0] + min(dp[i - 1][1], dp[i - 1][2])
        dp[i][1] = cost[i][1] + min(dp[i - 1][0], dp[i - 1][2])
        dp[i][2] = cost[i][2] + min(dp[i - 1][0], dp[i - 1][1])
    return min(min(dp[n-1][0], dp[n-1][1]), dp[n-1][2])

init()
print(RGB())