문제
N명이 원형으로 앉아 있을 때, 인접한 사람끼리만 악수할 수 있는 경우의 수의 일의 자리를 구하라.
입력
사람 수 N이 주어진다.
출력
경우의 수의 일의 자리를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 | 3 |
풀이
피보나치 수열의 점화식을 이용하여 일의 자리만 추적한다.
f(1) = 1,f(2) = 2로 초기화한다f(n) = f(n-1) + f(n-2)점화식으로 계산한다- 일의 자리만 필요하므로 매 단계 mod 10을 적용한다
핵심 아이디어: 인접한 쌍에서 악수 여부를 독립적으로 선택하면 피보나치 수열이 되며, 일의 자리는 주기 60으로 반복된다.
코드
x = int(input())
a, b = 1, 2
if x == 1:
print(a)
elif x == 2:
print(b)
else:
for i in range(x - 2):
a, b = b, (a + b) % 10
print(b)복잡도
- 시간: O(N)
- 공간: O(1)