RGB 거리-파이썬 생각과정

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

1149번: RGB거리

푸는데 구현조차 하지못했다

4     1 6
2     1 3
100   1 108
10000 1 10000

RGB중에 최소값을 고르고(문명6고르고아님 ㅎ) 다음줄에서는 겹치지는 색깔중에 가장 작은것을 고른다

간단한 동적계획법이다

 

위의 예시를 보면 위와같은 방식은 틀린것을 알수있다

 

개선안으로

i최소값+ i색깔과 다른 i+1의 최소값과

i+1최소값 i+1색깔과 다른 i의 최소값과 비교

채택할시

 

i까지의 최소값을 구하더라도 i+1에서 처음부터 다시구해야될수도있다

 

다른방법으로 가능한 모든 조합을 리스트에 담은뒤 거기서 최소값을 찾는 방법도 생각해보았는데 그러면 엄청~나게 많은경우의수가나오게된다 2의 1000승

마땅한방법이 생각나지않아 인사이트를 얻기위해 검색

 

출처

https://pacific-ocean.tistory.com/147

핵심은 줄마다 색깔별로 선택할때의 각각 최소값을 도출하라는것

그렇게하면 이미 구한 최소값에서 전단계로 다시 되돌아갈필요가없다

진정한 동적계획법이다

 

코드로구현

# RGB거리
import sys
input=sys.stdin.readline
N=int(input())
R,G,B=map(int,input().split())
d=[[R,G,B]]
for i in range(1,N):
    R,G,B=map(int,input().split())
    a=R+min(d[i-1][1],d[i-1][2])
    b=G+min(d[i-1][0],d[i-1][2])
    c=B+min(d[i-1][0],d[i-1][1])
    d.append([a,b,c])

print(min(d[-1]))

동적계획법은 정말 신세계인것같다