81. Python 백준 1149 번 RGB 자세한 설명

안녕하세요 코딩하는 덕구입니다.

다이나믹 프로그래밍 문제인 1149 번 RGB 파이썬 자세한 설명입니다.

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

1149번: RGB거리

 

 

먼저 1149번 정답 파이썬 코드입니다.

N = int(input())
cost = []

for i in range(N):
    cost.append(list(map(int, input().split())))

for i in range(1, N):
    cost[i][0] += min(cost[i - 1][1], cost[i - 1][2])
    cost[i][1] += min(cost[i - 1][0], cost[i - 1][2])
    cost[i][2] += min(cost[i - 1][0], cost[i - 1][1])

print(min(cost[N - 1][0], cost[N - 1][1], cost[N - 1][2]))

 

R, G, B 3 가지의 색으로 집을 칠하는 비용이 주어지고,

이전에 칠했던 색으로는 연속으로 색을 칠할 수 없는 조건 속에서

모든 집을 최소한의 비용으로 칠해야 됩니다.

 

어떤 색을 먼저 칠했느냐에 따라서 최소 비용이 달라지고,

우리는 계산해보기 전까지 알 수 없으므로 3가지의 경우를 모두 계산해본 후 

그 중 최소값을 선택해야 됩니다.

 

그럼 위의 직관을 코드로 구현해봅시다.

 

집의 개수 N 을 입력받고, 모든 비용을 저장할 리스트 cost를 생성하고, 값을 입력받아 모두 저장합니다.

N = int(input())
cost = []

for i in range(N):
    cost.append(list(map(int, input().split())))

이제 cost에는

0번 집부터 N-1번 집까지 총 N개의 집이 R, G, B 3가지의 색으로 칠해지는 비용이 저장되어 있습니다.

 

i번째 집을 R로 칠한다고 생각해봅시다.

그렇다면 i-1 번째 집은 G 혹은 B 로 칠해져 있어야 됩니다.

 

그럼 i번째 집을 G로 칠한다고 생각해봅시다.

그렇다면 i-1 번째 집은 R 혹은 B 로 칠해져 있어야 됩니다.

 

마지막으로 i번째 집을 B로 칠한다고 생각해봅시다.

그렇다면 i-1 번째 집은 R 혹은 G 로 칠해져 있어야 됩니다.

위의 직관을 가지고 i번째 집 까지 색을 겹치지 않고 칠하는 최소 비용은

마지막 색이 R인 경우

R + (i - 1 번째 집 까지 색을 겹치지 않고 최소한의 비용으로 칠하면서 마지막에 칠해진 색이 G 혹은 B)

cost[i][0] += min(cost[i - 1][1], cost[i - 1][2])

 

마지막 색이 G인 경우

G + (i - 1 번째 집 까지 색을 겹치지 않고 최소한의 비용으로 칠하면서 마지막에 칠해진 색이 R 혹은 B)

cost[i][1] += min(cost[i - 1][0], cost[i - 1][2])

 

마지막 색이 B인 경우

B + (i - 1 번째 집 까지 색을 겹치지 않고 최소한의 비용으로 칠하면서 마지막에 칠해진 색이 R 혹은 G)

cost[i][2] += min(cost[i - 1][0], cost[i - 1][1])

 

가 됩니다.

 

이렇게 마지막에 칠해진 색이 R, G, B 인 경우 3가지를 반복적으로 구해서

최소값을 출력해주면 됩니다.

print(min(cost[N - 1][0], cost[N - 1][1], cost[N - 1][2]))

 

백준 1149번 파이썬 최종 코드입니다.

N = int(input())
cost = []

for i in range(N):
    cost.append(list(map(int, input().split())))

for i in range(1, N):
    cost[i][0] += min(cost[i - 1][1], cost[i - 1][2])
    cost[i][1] += min(cost[i - 1][0], cost[i - 1][2])
    cost[i][2] += min(cost[i - 1][0], cost[i - 1][1])

print(min(cost[N - 1][0], cost[N - 1][1], cost[N - 1][2]))

 

이상으로 백준 1149번 자세한 설명과 함께 파이썬 코드였습니다.

감사합니다.