코드

n = int(input())

# DP 테이블 초기화
# d[0] = 그냥 0
d = [0] * 91
d[1] = 1 # 1개
d[2] = 1 # 2개

# n의 범위 1 ~ 90
for i in range(3, 91):
    # 점화식
    d[i] = d[i-2] + d[i-1]
    
print(d[n])

문제 해설

DP 문제.

처음에 문제를 접근했을 때는 별 규칙을 찾지 못하였다. 그래서 일단 n의 값에 따른 이친수의 개수를 직접 세어보니 규칙이 보였는데 규칙은 아래와 같다.

현재 이친수의 개수 = 이전 이친수의 개수 + 2단계 전 이친수의 개수

혹시나 싶어서 n=5일 때까지 직접 구해보고 확신을 얻어 점화식을 작성하여 문제를 풀어보니 정답으로 인정받았다.

댓글남기기

참고