[Gold IV] RGB거리 2 - 17404 (DP)

[Gold IV] RGB거리 2 - 17404

문제 링크

성능 요약

메모리: 30840 KB, 시간: 112 ms

분류

다이나믹 프로그래밍(dp)

문제 설명

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

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

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

풀이방법

문제를 보고 dp라는 것을 알게 되었고, 규칙을 토대로 구현해보려 시도했지만, 실패하고 풀이를 참조했다.

풀이를 보기 전에 첫 번째로, 규칙을 고려했을 때 1번 집의 색과 N번 집의 색은 무조건 달라야 하며 i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 달라야 하므로, 인접한 것끼리는 색을 다르게 하면 되었다. 정리하자면,

1. 첫 번째 집과 마지막 번째 집의 색상은 달라야한다.

2. 인접한 집끼리 색상은 달라야한다.

이 두가지를 지켜주면 된다.

그러나 최솟값을 구해야 했으므로, 첫 번째 집을 각각의 빨, 초, 파 3가지 색상의 경우의 수를 구현해야 할 것 같다고 생각을 했는데 이 부분은 맞았다. 그러나, 구현을 포기했던 문제점은..

첫 번째로, 규칙에 맞게 모든 색상을 다 배치했을 때 배치가 잘 됐는지 유효성 검사를 어떻게 할 지.. 아이디어를 떠올리지 못했고, 두 번째로, 첫 번째 집을 세 가지 색상의 경우의 수로 다 배치했을 때 유효한 것들 중 어떤 게 제일 최솟값일지 복잡도를 최대한 줄여 구현할 방법을 찾지 못해서 풀지 못하였다.

첫 번째 문제점의 해결 방법은 첫 번째 집을 빨, 초, 파 세 가지 경우의 수로 나누면서 dp를 3번 초기화를 해줬기 때문에 각 인덱스마다 색상별로 최솟값을 다 저장할 수 있어서 자연스레 해결이 된다.

두 번째 문제점의 해결 방법은 첫 번째 집을 빨, 초, 파 세 가지 경우의 수로 나눌 때의 인덱스와(인덱스 == 색상) 다른 인덱스(색상)일 경우만 판단하여 최솟값을 초기화시켜주면 해결이 가능하다.

 

참고로, answer와 dp에 최댓값을 1000000으로 한 이유는 N의 범위가 1000까지이며, 비용도 1000이 최대이므로 가장 최댓값이 나올 경우는 1000x1000이라 생각하여 이렇게 정했다.

n = int(input())
color = []
answer = 1000000
for i in range(n):
    red, green, blue = map(int,input().split())
    color.append([red, green, blue])
for i in range(3):
    dp = [[1000000, 1000000, 1000000] for _ in range(n)]
    dp[0][i] = color[0][i]
    for j in range(1,n):
        dp[j][0] = color[j][0] + min(dp[j-1][1], dp[j-1][2])
        dp[j][1] = color[j][1] + min(dp[j-1][0], dp[j-1][2])
        dp[j][2] = color[j][2] + min(dp[j-1][0], dp[j-1][1])
    for k in range(3):
        if i != k: #1번과 N번의 색상이 다를 경우만
            answer = min(answer, dp[-1][k])
print(answer)