[백준] 1149번 RGB거리 파이썬 풀이

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

 

 

1. 풀이

• (n - 1)번째 결과를 바탕으로 가장 최소 비용을 만드는 n번째 선택을 하자.

이전 결과를 담을 2차원 리스트가 필요하다. 행은 몇 번째 집인지를 의미하고, 열은 R(0), G(1), B(2) 중 어떤 색을 선택했는지에 대한 정보를 나타낸다.

 

 

위 그림은 백준의 첫 번째 입력 예제를 바탕으로 만들어진 2차원 리스트이다.
예를 들어 1번 집을 초록색과 파란색 중 더 비용이 작은 색을 칠하고, 2번 집에 빨강(R)을 칠한다면 그 비용은 dp[1][0]에 담긴다. 이를 식으로 나타내면 dp[1][0] = min(dp[0][1], dp[0][2]) + COSTS[1][0]이다.

그런데 사실 2번 집에 빨간색이 아니라, 초록색 혹은 파란색을 칠해야만 최소 비용이 될 수도 있다. 따라서 2번째 집에 초록색과 파란색을 칠하는 경우도 계산해서 dp 리스트에 저장해두어야 한다. 이를 점화식으로 나타내면 다음과 같다.

dp[0][0] = COSTS[0][0]
dp[0][1] = COSTS[0][1]
dp[0][2] = COSTS[0][2]

dp[n][0] = min(dp[n - 1][1], dp[n - 1][2]) + COSTS[n][0]
dp[n][1] = min(dp[n - 1][0], dp[n - 1][2]) + COSTS[n][1]
dp[n][2] = min(dp[n - 1][0], dp[n - 1][1]) + COSTS[n][2]

2. 정답 코드

N = int(input())
COSTS = []
for _ in range(N):
    COSTS.append(list(map(int, input().split())))

dp = [[0, 0, 0] for _ in range(N)]
dp[0][0] = COSTS[0][0]
dp[0][1] = COSTS[0][1]
dp[0][2] = COSTS[0][2]

for n in range(1, N):
    dp[n][0] = min(dp[n - 1][1], dp[n - 1][2]) + COSTS[n][0]
    dp[n][1] = min(dp[n - 1][0], dp[n - 1][2]) + COSTS[n][1]
    dp[n][2] = min(dp[n - 1][0], dp[n - 1][1]) + COSTS[n][2]

print(min(dp[N - 1]))