1149: RGB거리

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

1149번: RGB거리

설명

우선, 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구하자. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야한다.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2<=i<=N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

• 이때, N번 집의 색은 N-1번 집의 색과 같지 않아야한다. 는 조건이 있기 때문에 다음 입력값이 R일때, G일때, B일때 이렇게 3가지 경우로 나누어 계산해야한다. 2번째 입력값이 R(49)일 때 이전 입력값인 G(40)와 B(83)의 값을 비교하여 최솟값을 구하고 현재 자신의 값과 더해주는 방식으로 계산을 진행한다. 

핵심 아이디어

• 다이나믹 프로그래밍
• 첫번째는 계산하지 않고 두번째 부터 시작해서 빨간집인 경우, 초록집인 경우, 파란집인 경우를 계산하는데 이전의 값들 중 같은 색을 제외한 min을 더해주는 걸 반복한다.
• 현재 집을 각각 빨/초/파로 색칠할 때 이와 겹치지 않는 색을 칠한 이전 집 중 최소 비용을 구해 현재 집의 비용을 더해주면 된다.
• 결국 빨강, 초록, 파랑 집을 선택한 모든 경우에 대해 최솟값만이 더해져서 나오는게 되며 그 중에서 최솟값을 선택하면 된다.

코드 구현

# 다이나믹 프로그래밍
n = int(input())

# 각 집마다 비용 입력받기
RGB = [list(map(int, input().split())) for _ in range(n)]

# 두번째 집 부터 확인
for i in range(1, n):
	# 만약 빨간집이 최소라면
	RGB[i][0] = min(RGB[i-1][1],RGB[i-1][2]) + RGB[i][0]
	# 만약 초록집이라면
	RGB[i][1] = min(RGB[i-1][0], RGB[i-1][2]) + RGB[i][1]
	# 만약 파란집이라면
	RGB[i][2] = min(RGB[i-1][0], RGB[i-1][1]) + RGB[i][2]
# for loop 다 돌고 마지막 출력
print(min(RGB[n-1]))

C++

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int RGB[1001][3] = {0,};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	// i번째 집을 빨강, 초록, 파랑으로 칠 했을 때의 비용의 최소값을 구해
	// 나가는 것
	int n;
	cin >> n;
	RGB[0][0] = 0;
	RGB[0][1] = 0;
	RGB[0][2] = 0;
	// 첫번째 집부터 확인하면서 모든 집을 칠하는 최솟값을 업데이트 해 나간다.
	for (int i = 1; i <= n; i++) {
		cin >> RGB[i][0] >> RGB[i][1] >> RGB[i][2];

		// i번째 집을 빨강색으로 칠할 때의 최소비용
		RGB[i][0] = min(RGB[i - 1][1], RGB[i - 1][2]) + RGB[i][0];
		//i번째 집을 초록색으로 칠할 때의 최소비용
		RGB[i][1] = min(RGB[i - 1][0], RGB[i - 1][2]) + RGB[i][1];
		// i번째 집을 파란색으로 칠할 때의 최소비용 저장
		RGB[i][2] = min(RGB[i - 1][0], RGB[i - 1][1]) + RGB[i][2];
	}
	// 마지막 집을 칠했을 때의 최소 비용 중 가장 작은 값
	cout << min(RGB[n][0], min(RGB[n][1], RGB[n][2]));

}