[백준] 2193-이친수

문제바로가기

N까지 숫자가 증가할 때 경우의 수를 따져보자

1	2	3	4	5	6	...	N
1	1	2	3	5	8	...	n[N-2]+n[N-1]

다음과 같은 규칙을 찾을 수 있다.

N = int(input())

if N == 1 or N == 2:
    print(1)
else:
    n = [1]*N
    n[0] = n[1] = 1
    for i in range(2, N):
        n[i] = n[i-2] + n[i-1]

    print(n[N-1])