[백준/Python] 17404번: RGB거리 2

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

17404번: RGB거리 2

---

---

문제 분석

각 집의 색은 이전, 이후의 집과 색이 달라야 한다.

집의 색이 정해진다면 비용을 누적하여 가장 작은 비용을 출력하면 된다.

 

기준이 없으므로 1번 집부터 색을 칠한다고 가정했을 때,

1번 집의 색이 빨강이라면 2번 집은 초록과 파랑 중 골라야하고 N번 집도 초록과 파랑 중 골라야 한다.

 

1149번: RGB거리 문제

위의 문제의 경우는 자기 자신의 바로 다음 집과 같지만 않으면 순서대로 내려오면서 판단할 수 있었다.

 

하지만 지금의 문제는 첫 번째 집이 마지막 집과 색이 달라야 하기 때문에 두 개의 집 중 하나의 집이 기준이 되어야 한다.

따라서 1번 집을 기준으로 하여 다이나믹 프로그래밍 알고리즘을 통해 비용을 누적하는 것이 이 문제의 핵심이 된다.

 

우선 리스트를 만들 때 ['빨강', '초록', '파랑']이 올 수 있도록 3개의 원소를 갖는 N개의 2차원 배열을 선언한다.

그리고 첫 번째 집이 빨강, 초록, 파랑일 때로 나누어 비용을 누적 계산한 뒤, 가장 작은 값이 정답이 될 수 있도록 한다.

 

첫 번째 집이 빨강이라면

0번째 인덱스에 빨강의 비용을 넣고 나머지 비용은 최댓값을 넣는다.

그렇게 된다면 두 번째 집에서 최소 비용을 계산하기 위해서는 무조건 첫 번째 집은 빨강색이라고 생각하고 비용을 계산하게 될 것이다.

마지막 N번째 집을 짓는 비용이 모두 계산이 되고 나면 총 비용이 나오는데

이 때 총 비용에서 0번째 인덱스를 제외한 1번째, 2번째 비용 중 최소를 가지고 현재 저장된 답과 비교하면 된다.

즉 마지막 집이 빨강이 아닌 초록과 파랑 중 최종 비용을 정하면 되는 것이다.

 

---

코드

MAX = 1000 * 1000 + 1

n = int(input())

cost = []
dp = [[0 for _ in range(3)] for _ in range(n)]
answer = MAX

for _ in range(n):
    cost.append(list(map(int, input().split())))

for k in range(3):
    for i in range(n):
    	# 첫 번째 집이 k라면 마지막 집은 k가 되면 안됨
        if i == 0:
            dp[i] = [MAX, MAX, MAX]
            dp[i][k] = cost[0][k]
        else:
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0]
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1]
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2]

    for i in range(3):
    	# 최종 비용에서 첫 번째 집과 마지막 집의 색이 달라야 하기 때문에
        if i == k:
            # 같은 경우는 continue로 넘어감
            continue
            
        answer = min(answer, dp[n - 1][i])

print(answer)