[伯俊/Python]149 RGB距離
6389 ワード
https://www.acmicpc.net/problem/1149
アルゴリズム分類
問題を解く
最初は0号室で最小値の色を選んで解きました.
以下の反例で失敗した.
ex)
2
100 1 100
9991 999->101
1号室でRを選んだら、0号室はG、Bの中で最小値を選んだはずです.その値段と原価を合計し続けます.
1号室でGを選んだら、0号室はR、Bの中で最小値を選びます...
ex)
49=min(40,83)+49=89
60=min(26,83)+60=86
57=min(26,40)+57=83
26 40 83
49 60 57
13 89 99
↓
26 40 83
89 86 83
13 89 99
ソースコード
n=int(input())
cost=[]
for i in range(n):
cost.append(list(map(int, input().split())))
for i in range(1,n):
cost[i][0]=min(cost[i-1][1], cost[i-1][2])+cost[i][0]
cost[i][1]=min(cost[i-1][0], cost[i-1][2])+cost[i][1]
cost[i][2]=min(cost[i-1][0], cost[i-1][1])+cost[i][2]
print(min(cost[n-1]))Reference
この問題について([伯俊/Python]149 RGB距離), 我々は、より多くの情報をここで見つけました https://velog.io/@bye9/백준파이썬-1149-RGB거리テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol