백준 2193번 이친수

문제 링크

문제 전략

• d[N][i] : 길이가 N이고 마지막에 오는 숫자가 i일때 이친수의 갯수 라고 하고 점화식을 세운다.
• 조건에 맞는 초기조건과 , 예외가 발생하는 경우를 잘 처리한다.

알고리즘 종류

• 다이나믹 프로그래밍

N = int(input()) # 1<=N<=90
d = [[0]*2 for _ in range(N+1)]
d[1] = [0,1]


for i in range(2,N+1): 
  for j in range(0,1+1): #j: 0 , 1 

    if j ==0:
      d[i][j] = d[i-1][0] + d[i-1][1]
    elif j ==1:
      d[i][j] = d[i-1][0]

result = sum(d[N])
print(result)

---

모범답안

d = [0]*91
n = int(input())
d[1] = 1
d[2] = 1
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]
print(d[n])