2193. 이친수

문제 코드

N = int(input())

zero_list = [0]*(N+1)
one_list = [0]*(N+1)

one_list[1] = 1

for i in range(2,N+1):
    one_list[i] = zero_list[i-1]
    zero_list[i] = one_list[i-1]+zero_list[i-1]

result = one_list[N] +zero_list[N]

print(result)

문제 풀이

• 이전 값이 0이었다면 0과 1 모두 붙을수 있고, 1이었다면 0만 붙을수 있다.
• 따라서 zero list와 one list를 두어서 점화식 계산을 하도록 했다.
• 정연이가 알려줬는데 피보나치랑 똑같더라

  zero_list[i]+one_list[i] =a[i]
  zero_list[i] = a[i-1]
  one_list[i-1] = zero_list[i-2] = a[i-2]
  a[i] = a[i-1]+a[i-2]