【伯俊】1107番:リモコン回答

質問する
秀斌はテレビを見ています.秀斌はチャンネルを変えようとしたが、ボタンを強く押しすぎて、数字のボタンが壊れた.
リモコンのボタンは0から9まで数字+と-があります.クリックすると、現在表示されているチャンネルから+1チャンネルに移動し、-をクリックして-1チャンネルに移動します.チャンネル0で-を押すと、チャンネルはそのままで、チャンネルは無限大になります.
スビンが今移動するチャンネルはNです.ボタンに障害が発生した場合は、Nチャンネルに移動するには何回ボタンを押す必要があるかを尋ねるプログラムを作成します.
秀彬が今見ているチャンネルは100番です.
入力
第1行は、スビンが移動するチャンネルN(0≦N≦500000)を与える.2行目には、障害ボタンの個数M(0≦M≦10)が与えられる.障害が発生したボタンがある場合は、3行目に障害が発生したボタンが表示され、同じボタンは複数回表示されません.
しゅつりょく
チャネルNに移動するには、最初の行の出力で少なくとも何回ボタンを押す必要がありますか.
方法
この問題はブロトプスを探索する必要がある問題であり,範囲内のすべての可能な数字を比較することで,最小キー回数を求めればよい.
障害のないボタンを範囲内で作成し、数値とターゲットチャネルの違いを求めることができるかどうかを確認します.
ここで重要なのは、低数字から上がる場合と、高数字から下がる場合を考えることです.
最大入力可能なN、すなわち500000が入力された場合、50万〜100000の間の最小回数は、1〜500000の間の最小回数よりも少なくなる可能性がある.
完全なコード

from sys import stdin
input = stdin.readline

N = int(input())
M = int(input())

# 망가진 버튼이 없으면 리스트 입력 받지 않음
if M > 0:
    broken_button = list(map(str, input().split()))
else:
    broken_button = []

# 이동하려는 채널이 시작 채널과 같으면 0
if N == 100:
    print(0)
else:
    # 최대 횟수는 목표 채널까지 +만 눌렀을 때의 횟수
    minCnt = abs(N - 100)
    # 입력 제한은 500000이지만
    # 1부터 500000까지의 차이와
    # 1000000부터 500000까지의 차이도 고려해야함
    for num in range(1000001):
        possible = True
        # 모든 경우의 수를 검사하면서
        # 해당 숫자가 고장난 버튼의 숫자인지 검사
        for i in str(num):
            if i in broken_button:
                possible = False
                break
        # 가능한 숫자라면
        if possible:
            # 최소 횟수는 숫자버튼을 누르는 횟수와 +혹은-를 누르는 횟수의 합
            minCnt = min(minCnt, len(str(num)) + abs(num - int(N)))

    print(minCnt)

アルゴリズムが全く知られていなかった時代には、すべての問題がBrout Forsで接近していたのですが、最近はBrout Forsで接近したくない傾向にあるので、接近方法を探すのに少し時間がかかりました.