[백준] 11727번 (python 파이썬)

n = int(input())

d = [0, 1, 3, 5]

if n < 4:
    print(d[n])
else:
    for i in range(4, n + 1):
        d.append((d[i - 1] + 2*d[i - 2]) % 10007)
    print(d[n])

 

어떤식으로 해야 될지 몰랐는데 

가장 뒤에 올 수 있는 경우의 수를 기준으로 잡고 

생각하면 쉽게 풀린다

파란색은 차례대로 d(n - 1), d(n - 2), d(n - 2)

일 때를 얘기 한다

 

따라서 d[n] = d[n - 1] + 2*[n - 2] 식을 만들 수 있다