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

백준 1149번 파이썬 RGB 거리 문제 풀이 입니다.

파이썬 RGB 거리 문제 풀이

문제 설명

문제 출처: https://www.acmicpc.net/problem/1149

문제 풀이 (정답 코드)

n = int(input())

houses = []
for i in range(n):
  a,b,c = map(int,input().split())
  houses.append(list([a,b,c]))

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

print(min(houses[n-1][0], houses[n-1][1], houses[n-1][2]))

다이나믹 프로그래밍으로 풀 수 있다. 두번째 집부터 시작해서, 첫번째 집에서 지금 색칠한 집과 다른색으로 칠한 두 값 + 현재 색깔 집의 최소값을 구한 뒤 저장한다. 이렇게 하면 i번째 집이 각각 빨강, 초록, 파랑일때의 최소값을 알 수 있다. 같은 작업을 n번째 집까지 반복해준뒤 n번째 집의 RGB값의 최소값을 구하면 정답이다.

 

맺으며

DP문제는 다 새로 테이블을 만들어서 푸어야 되는 줄 알고 리스트를 만들었는데, 처음 입력했던 값에서 업데이트 해나가는 점이 신기했다.