문제 설명
다음과 같이, n개의 계단이 있다. 아래는 n=4일 때의 예시이다.
현재 0번째 계단에 서 있고, 한 번에 한 개 또는 두 개의 계단을 올라갈 수 있다.
n개의 계단을 올라갈 수 있는 서로 다른 방법의 개수를 구하여라.
이때, 수가 커질 수 있으므로 개수의 마지막 네 자리,
즉 10000으로 나눈 나머지를 대신 출력하라.
직접 큰 수를 구해서 나눌 수는 없으므로, 아래 식을 이용하라.
(a + b) % m = (a % m + b % m) % m
현재 0번째 계단에 서 있고, 한 번에 한 개 또는 두 개의 계단을 올라갈 수 있다.
n개의 계단을 올라갈 수 있는 서로 다른 방법의 개수를 구하여라.
이때, 수가 커질 수 있으므로 개수의 마지막 네 자리,
즉 10000으로 나눈 나머지를 대신 출력하라.
직접 큰 수를 구해서 나눌 수는 없으므로, 아래 식을 이용하라.
(a + b) % m = (a % m + b % m) % m
입력 설명
첫째 줄에 계단의 개수 n이 주어진다. (1 <= n <= 105)
출력 설명
첫째 줄에 서로 다른 방법의 개수를 10000으로 나눈 나머지를 출력한다.
입력 예시 Copy
4
출력 예시 Copy
5
도움
n=4일 경우, 다음과 같이 5개의 방법이 존재한다.
1+1+1+1
2+1+1
1+2+1
1+1+2
2+2
1+1+1+1
2+1+1
1+2+1
1+1+2
2+2