[Python] 17404 - RGB거리 2

[Gold IV] RGB거리 2 - 17404 

[문제 링크](https://www.acmicpc.net/problem/17404)

🗝️알고리즘 분류

• 다이나믹 프로그래밍

---

💻문제 정의

N개의 집을 R, G, B 색상 중 하나로 색칠하려 할 때, 앞, 뒤의 집과 색상이 다르도록 하는 최소 비용을 구하는 문제이다.

 

💡접근 및 설계

다이나믹 프로그래밍 방식으로 문제를 해결하였다.

 

문제에서 핵심은 첫 번째 집의 색상의 여부에 따라 마지막집의 색상이 결정되기에 세 가지의 case를 두어 모든 case에서 최소 비용을 구하도록 설계하였다.

 

✏️알고리즘 풀이

INF = 1_000_000_000

first = list(map(int, input().split()))
dp_1 = [first[0], INF, INF] # 첫번째 집이 R인 경우
dp_2 = [INF, first[1], INF] # 첫번째 집이 G인 경우
dp_3 = [INF, INF, first[2]] # 첫번째 집이 B인 경우

먼저 첫 번째 집에 대한 세 가지 경우를 지정하였다.

 

# 2 ~ N-1 번째 집은 이전의 집 색과 다른 색만을 칠하면 됨
for _ in range(N-2):
    rgb = list(map(int, input().split()))
    dp_1 = [rgb[0] + min(dp_1[1:]), rgb[1] + min(dp_1[0], dp_1[2]), rgb[2] + min(dp_1[:2])]
    dp_2 = [rgb[0] + min(dp_2[1:]), rgb[1] + min(dp_2[0], dp_2[2]), rgb[2] + min(dp_2[:2])]
    dp_3 = [rgb[0] + min(dp_3[1:]), rgb[1] + min(dp_3[0], dp_3[2]), rgb[2] + min(dp_3[:2])]

각 경우에 대해 2 ~ N-1 번째 집의 색상을 결정한다.

이들의 경우는 이전의 집의 색상과 다르기만 하다면 자연스럽게 i번째 집의 색상은 i-1, i+1 번째 집의 색상과 다르게 된다.

 

# 마지막(N 번째)의 경우, 첫 번째 집과 색상이 달라야 함
last = list(map(int, input().split()))
dp_1 = [INF, last[1] + min(dp_1[0], dp_1[2]), last[2] + min(dp_1[:2])]
dp_2 = [last[0] + min(dp_2[1:]), INF, last[2] + min(dp_2[:2])]
dp_3 = [last[0] + min(dp_3[1:]), last[1] + min(dp_3[0], dp_3[2]), INF]

print(min(min(dp_1), min(dp_2), min(dp_3))) # 모든 케이스에서 최솟값 출력

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

각 경우에 맞게 해당 자리를 INF로 두어 선택하지 못하게 한다.

 

🗒️제출 코드

# 17404 RGB 거리

N = int(input())

INF = 1_000_000_000

first = list(map(int, input().split()))
dp_1 = [first[0], INF, INF] # 첫번째 집이 R인 경우
dp_2 = [INF, first[1], INF] # 첫번째 집이 G인 경우
dp_3 = [INF, INF, first[2]] # 첫번째 집이 B인 경우

# 2 ~ N-1 번째 집은 이전의 집 색과 다른 색만을 칠하면 됨
for _ in range(N-2):
    rgb = list(map(int, input().split()))
    dp_1 = [rgb[0] + min(dp_1[1:]), rgb[1] + min(dp_1[0], dp_1[2]), rgb[2] + min(dp_1[:2])]
    dp_2 = [rgb[0] + min(dp_2[1:]), rgb[1] + min(dp_2[0], dp_2[2]), rgb[2] + min(dp_2[:2])]
    dp_3 = [rgb[0] + min(dp_3[1:]), rgb[1] + min(dp_3[0], dp_3[2]), rgb[2] + min(dp_3[:2])]

# 마지막(N 번째)의 경우, 첫 번째 집과 색상이 달라야 함
last = list(map(int, input().split()))
dp_1 = [INF, last[1] + min(dp_1[0], dp_1[2]), last[2] + min(dp_1[:2])]
dp_2 = [last[0] + min(dp_2[1:]), INF, last[2] + min(dp_2[:2])]
dp_3 = [last[0] + min(dp_3[1:]), last[1] + min(dp_3[0], dp_3[2]), INF]

print(min(min(dp_1), min(dp_2), min(dp_3))) # 모든 케이스에서 최솟값 출력

---

💭오늘의 회고

이전에 풀어보았던 내려가기 문제와 비슷한 느낌의 문제였다. 차이점이라면 해당 문제는 내려온 방향에 따라 인접한 곳으로 내려갈 수 있었던 반면, 이번 문제는 내려왔던 방향을 제외한 나머지 방향으로 내려가는 느낌이었다.

 

첫번째 집의 색상에 따라 마지막 집의 색상이 결정된다는 것을 구현하는 부분이 힘들었으나, 어찌저찌 통과가 된게 신기했던 문제였다...!