pythonでコーディング問題を解く6

続き

問題1 050 - Stair Jump

stairs, steps = list(map(int, input().split(' ')))

# 0段目から移動するパターンもあるため、階数+1で初期化する必要がある
patterns = [0] * (stairs + 1)

for i in range(len(patterns)) :
    # 0段目は必ず1
    if i == 0 :
        patterns[i] = 1
    # stepsより小さい段数は1段ずつ上っていく以外に到達方法がないので1になる
    elif i < steps :
        patterns[i] = patterns[i - 1]
    # steps以上の場合
    # 1段前から1段上るか、steps数段前からsteps段登るかの2パターンがある
    # つまり、1段前に到達する方法と、steps数段前に到達する方法の合計が、今の段に到達する方法になる
    else :
        patterns[i] = patterns[i - 1] + patterns[i - steps]
        
print(patterns)

問題2 C - Typical Stairs

stairs, broken_stairs_count = list(map(int, input().split(' ')))

patterns = [1] * (stairs + 1)
broken_stairs = []
MOD = 1000000007

for i in range(broken_stairs_count) :
    broken_stairs.append(int(input()))
    
print (broken_stairs)

# 1段目が壊れている場合、1段目に到達する方法は0
patterns[1] = 0 if 1 in broken_stairs else 1

# 2段目以降は、
# 壊れていなければ、ひとつ前と二つ前の段に到達する方法の合計
# 壊れていれば、その段に到達する方法は0
for i in range(2, len(patterns)) :
    if i in broken_stairs :
        patterns[i] = 0
    else:
        patterns[i] = patterns[i - 1] + patterns[i - 2]

print(patterns[-1] % MOD)