백준 1149: RGB거리 - 파이썬

RGB거리  성공

1149번: RGB거리

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

내 코드

 

import sys

n=int(sys.stdin.readline())

arr=[]
for _ in range(n): #색깔별 비용들 리스트로 받기
    arr.append(list(map(int, sys.stdin.readline().split())))

#이전 단계의 합들 중 최소값을 더하는 것이 최선이다
for i in range(1,n): #0단계가 아닌 1단계부터 시작. 1단계에서 0단계의 최소값들을 선택
    arr[i][0]+=min(arr[i-1][1],arr[i-1][2])
    arr[i][1]+=min(arr[i-1][0],arr[i-1][2])
    arr[i][2]+=min(arr[i-1][0],arr[i-1][1])

#배열의 마지막 값에 최종 색깔별로 최소값들이 있는데 그 중 최소가 답
answer=min(arr[n-1][0],arr[n-1][1],arr[n-1][2])
print(answer)

 

풀이 및 접근)

- 이런 누적합의 최소를 구하는 문제는 풀이가 거의 같다. 현재 값을 더하기 전에 이전의 누적 값들중 최소로만 합을 구성하는 로직이다.

- 위의 로직에서 색깔만 안 겹치도록 설계하면 크게 문제 없이 해결된다.