[Python]伯準/RGB距離/149/DP

6500 ワード
python baekjoon テキストリンク
DPコンセプトショートカット
質問する
RGB距離問題リンク
RGB街にはN軒の家がある.街は線分で表すことができ、1号室からN号室まで順番に表示されます.
家は赤、緑、青の中の色に塗らなければならない.各家に赤、緑、青の費用を塗るときは、以下のルールを満たし、すべての家の費用を塗る最高価格を見つけてみましょう.
  • 1号室の色は2号室の色と同じではありません.
  • N号の家の色はN-1号の家の色と同じではありません.
  • i(2≦i≦N-1)号住宅の色はi-1号、i+1号住宅の色と同じではない.
    • 入力
    1行目は家の数N(2≦N≦1000)を与えた.2行目から、N行目では、1軒ごとに赤、緑、青に塗った料金が1号から1行1つになります.家を塗る費用は1000以下の自然数です.
    3
26 40 83
49 60 57
13 89 99
    しゅつりょく
    最初の行には、すべてのブラシ住宅の費用の最高値が出力されます.
    96
    方法
    現在のRGBのいずれかの色を選択した場合、以前は現在の色を除いて、コストの中で小さいコストを選択しました.

  • 3 D配列で入力を受け入れる

  • 各色を複文で選択する場合、現在の色以外の色の最小コストを選択し、現在の値に加算します.

  • 最後のリストから最小の原価出力を選択

    • コード#コード#
    

# url : https://www.acmicpc.net/problem/1149
# 난이도 : silver 1

import sys
n = int(input())

num_lists = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]


# 이 전에 칠한 색을 제외한 비용 중 작은 값을 현재 비용과 더한다
for i in range(1, len(num_lists)):
    num_lists[i][0] += min(num_lists[i-1][1],num_lists[i-1][2])
    num_lists[i][1] += min(num_lists[i-1][0],num_lists[i-1][2])
    num_lists[i][2] += min(num_lists[i-1][0],num_lists[i-1][1])

print(min(num_lists[n-1]))
print(num_lists)
    せん断法の考察
    任意の場所にダイアログを表示