[알고리즘/DP] 1149번 : RGB 거리 - python

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

1149번: RGB거리

 

---

• 문제
• 소요시간: 30분 실패

 

---

• 설계하기(접근방법) 

1. 입력받기

rgb 배열을 입력받는다

 

2. 구현하기

그 다음 항의 최소합은

그 이전에 자기 자신 색깔을 제외한

나머지 두 색깔의 최소값 중 하나와 더한 값이다

 

이 것을 일반화 시키면

rgb[i][0] += min(rgb[i-1][1], rgb[i-1][2]) 와 같은 형태가 나온다

 

3. 출력하기

n-1 항의 최소값을 출력한다

 

 

---

• 코드(출력)

import sys
input = sys.stdin.readline

n = int(input())
rgb = [0 for _ in range(n)]

for i in range(n):
    rgb[i] = list(map(int,input().split()))

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


print(min(rgb[n - 1]))

---

• 얻어갈 부분

1. 역순으로 생각해보면 쉽게 떠올릴 수 있는 문제였지만, 일반화에 어려움을 겪었다