[python] 백준 17404번: RGB거리2(DP)

# 17404 RGB거리2

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

17404번: RGB거리 2

⭐ 코드

import sys
input = sys.stdin.readline
N = int(input())

house = [list(map(int, input().split())) for _ in range(N)]
INF = sys.maxsize

answer = INF
for i in range(3):
    dp = [[INF, INF, INF] for _ in range(N)]
    dp[0][i] = house[0][i]

    for j in range(1, len(house)):
        dp[j][0] = house[j][0] + min(dp[j-1][1], dp[j-1][2])
        dp[j][1] = house[j][1] + min(dp[j-1][0], dp[j-1][2])
        dp[j][2] = house[j][2] + min(dp[j-1][0], dp[j-1][1])
    
    for k in range(3):
        if i != k:
            answer = min(answer, dp[-1][k])

print(answer)

📝 풀이

RGB거리1을 풀었어서 2에 조건 하나가 추가되었길래 쉬울 줄 알았는데, DP는 역시 DP였다.. 너무 어려워서 구글을 참고해서 풀었다.

 

이번 문제의 핵심은 for문을 3번 돌면서 첫번째 for문에서는 첫번째 집을 R로 칠했을 때 최소비용을 dp에 저장하고, 두번째는 첫번째집을 G로 칠했을 때, 세번째는 첫번째집을 B로 칠했을 때의 최소비용을 dp에 저장하는 것이다.

 

이 문제의 조건들을 요약하면 아래와 같다.

1. 경우의 수는 빨,초,파 3가지이다.

2. 첫번째 집이 빨강일때는 마지막 집은 초록과 파랑 중 작은값을 찾아야하고 초록일때는 마지막 집이 빨강과 파랑 중 작은값, 파랑일때는 빨강과 초록 중 작은 값을 기록해준다.

3. 마지막 집의 경우의 수도 3가지이며 그 중 가장 최소 비용인 경우를 찾으면 된다.

🔓 정답 코드 뜯어보기

import sys
input = sys.stdin.readline

N = int(input())

house = [list(map(int, input().split())) for _ in range(N)]
INF = sys.maxsize

answer = INF

최솟값을 구할 것이므로 sys.maxsize(IMF) 통해서 최솟값을 갱신시켜준다.

for i in range(3):
    dp = [[INF, INF, INF] for _ in range(N)] # 
    dp[0][i] = house[0][i] # 처음 집을 색칠 

    for j in range(1, len(house)): # 2번째 집부터 R, G, B로 색칠했을 때 최소값 갱신
        dp[j][0] = house[j][0] + min(dp[j-1][1], dp[j-1][2])
        dp[j][1] = house[j][1] + min(dp[j-1][0], dp[j-1][2])
        dp[j][2] = house[j][2] + min(dp[j-1][0], dp[j-1][1])
    
    for k in range(3):
        if i != k: # 첫번째 집과 N번째 집이 다른 경우만
            answer = min(answer, dp[-1][k])

print(answer)

# dp
# [
# [9223372036854775807,9223372036854775807, 83], 
# [132, 143, 9223372036854775864], 
# [156, 221, 231]
]

3가지 색을 위해 for문을 3번 돌려주는데 dp[0][i] = house[0][i]에 i를 R,G,B라고 생각하면 될 것 같다. 새로운 색을 탐색할때는 dp를 다시 초기화시켜준다.

for j in range(1, len(house)): # 2번째 집부터 R, G, B로 색칠했을 때 최소값 갱신
        dp[j][0] = house[j][0] + min(dp[j-1][1], dp[j-1][2])
        dp[j][1] = house[j][1] + min(dp[j-1][0], dp[j-1][2])
        dp[j][2] = house[j][2] + min(dp[j-1][0], dp[j-1][1])

다음 반복문은 RGB거리 1편 문제랑 로직이 비슷하다. 2번째 집부터 R, G, B로 색칠했을 때 최소값을 dp에 기록시켜준다.

for k in range(3):
        if i != k: # 첫번째 집과 N번째 집이 다른 경우
            answer = min(answer, dp[-1][k])

print(answer)

마지막으로 i와 k가 같지 않은, 즉 첫번째 집과 N번째 집이 다른 경우만 answer값에 최솟값을 기록시켜준다. 최종적으로 answer를 출력해주면 정답이 된다.