[python]백준 1149 풀이

한상욱·2023년 8월 9일

[python]백준풀이모음

목록 보기

6/38

RGB거리

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

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

1번 집의 색은 2번 집의 색과 같지 않아야 한다.

N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.

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

입력

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

출력

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

풀이

조건에 대해서 먼저 생각하겠습니다. 세개의 조건은 한마디로 처음에 색칠한 집에 색은 그 다음에 색칠할 집의 색과 달라야 한다는 의미입니다.

빨강 - 파랑 - 빨강 - 초록 은 가능해도, 빨강 - 빨강 - 파랑 이렇게는 안된다는 의미죠.

현재 칠해야 되는 집의 색상을 칠하는 최솟값은 이전까지 칠했던 색상의 최솟값과 현재 색상의 가격을 더하는 게 될겁니다. 즉, 만약 현재 집을 빨간색으로 칠한다면, 이전에 파란색으로 칠한 가격과 초록색으로 칠한 가격을 비교해서 최솟값과 빨간색을 칠하는 가격을 더하면 됩니다. 이렇게 되면 다음과 같은 관계식을 알아낼 수 있습니다.

a_{i(red)} = min(a_{i-1(blue)}, a_{i-1(green)}) + a_{빨강을 칠하는 가격}

이 사항들은 다른 색도 적용됩니다. 이렇게 모든 경우를 계산해서 결과를 DP테이블에 저장하고, 가장 마지막에서 최솟값을 출력하면 정답을 도출할 수 있습니다.

import sys
input = sys.stdin.readline

price = [[0, 0, 0]]
n = int(input())
for _ in range(n):
    price.append(list(map(int, input().split())))

# DP 테이블 초기화
dp = [[0, 0, 0] for i in range(1001)]
dp[1][0] = price[1][0] # 빨강을 칠하는 최솟값 초기화
dp[1][1] = price[1][1] # 파랑을 칠하는 최솟값 초기화
dp[1][2] = price[1][2] # 초록을 칠하는 최솟값 초기화
for i in range(2, n+1):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + price[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + price[i][1]
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + price[i][2]

# 정답 출력
print(min(dp[n][0], dp[n][1], dp[n][2]))