[백준] 1149 RGB거리 파이썬 풀이(동적 계획법)

백준

 

문제

• n번째 집은 그 앞의 집과 색이 같으면 안된다.
• 그 뒤에 집이랑도 색이 같으면 안된다.

 

풀이

• 집의 개수가 주어지고 집마다 빨강, 초록, 파랑으로 칠할때의 값이 주어지는 것을 리스트로 만든다.
• 1번째 집이 빨간색으로 칠하는 비용은 p[0][0]이고
• 2번째 집이 파랑색으로 칠하는 비용은 p[1][2] 이런식으로
• 집이 한개만 있을때는 p[0][0] p[0][1] p[0][2] 중에서 가장 작은 것을 구하면 된다.
• 집이 두개 이상일때는 지금 집이 빨강일때 -> 전 집을 파랑으로 칠한것 or 초록으로 칠한 것 중에서 비용을 더한 것이 가장 작을때를 p[i][0]에 저장한다
• 지금 집이 초록일때, 파랑일때도 마찬가지로 계산하여
• p[i][0] p[i][1] p[i][2] 에 저장하고 그 중에서 가장 작은 값을 선택한다.

 

코드

n = int(input())
p = []
for i in range(n):
    p.append(list(map(int, input().split())))
for i in range(1, len(p)):
    p[i][0] = min(p[i - 1][1], p[i - 1][2]) + p[i][0]
    p[i][1] = min(p[i - 1][0], p[i - 1][2]) + p[i][1]
    p[i][2] = min(p[i - 1][0], p[i - 1][1]) + p[i][2]
print(min(p[n - 1][0], p[n - 1][1], p[n - 1][2]))