[백준] 1149번 : RGB거리 (파이썬)

문제

나의 답안

n=int(input())
arr=[]
for i in range(n):
    arr.append(list(map(int,input().split())))
    
for i in range(1,n):
    arr[i][0]=min(arr[i-1][1],arr[i-1][2])+arr[i][0]#빨
    arr[i][1]=min(arr[i-1][0],arr[i-1][2])+arr[i][1]#초
    arr[i][2]=min(arr[i-1][0],arr[i-1][1])+arr[i][2]#파
print(min(arr[n-1][0],arr[n-1][1],arr[n-1][2]))

접근 방법

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
  N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
  i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
  라는 조건에 따라 색상이 중복되면 안된다.
• dp문제이므로 arr라는 배열 안에 세가지 색상으로 칠할 때의 비용을 저장해놓고, 제일 작은 값을 출력해주면 된다.
• 각 색상으로 칠할 때의 비용은 현재 집 색상 비용 + min(다른 색상 비용1, 다른 색상 비용2) 이 된다. 현재 집에서 각 색상을 칠했을 때의 최솟값을 저장하는 것이다.

다시 풀어보기!