문제 설명
한 걸음에 1미터 또는 2미터 또는 3미터를 이동할 수 있는 로봇이 있다.
이 로봇이 n미터를 이동할 수 있는 방법의 수를 구하여보자.
로봇이 1미터를 이동하는 방법은 1가지가 있다.
로봇이 2미터를 이동하는 방법은 1미터로 2번 이동하는 방법, 2미터로 1번 이동하는 방법 2가지가 있다.
로봇이 3미터를 이동하는 방법은
- 1미터를 한 걸음에 이동한 후 남은 2미터를 이동하는 방법: 2가지
- 2미터를 한 걸음에 이동한 후 남은 1미터를 이동하는 방법: 1가지
- 3미터를 한 걸음에 이동하는 방법: 1가지
총 4가지가 있다.
이 로봇이 n미터를 이동할 수 있는 방법의 수를 구하여보자.
로봇이 1미터를 이동하는 방법은 1가지가 있다.
로봇이 2미터를 이동하는 방법은 1미터로 2번 이동하는 방법, 2미터로 1번 이동하는 방법 2가지가 있다.
로봇이 3미터를 이동하는 방법은
- 1미터를 한 걸음에 이동한 후 남은 2미터를 이동하는 방법: 2가지
- 2미터를 한 걸음에 이동한 후 남은 1미터를 이동하는 방법: 1가지
- 3미터를 한 걸음에 이동하는 방법: 1가지
총 4가지가 있다.
입력 설명
로봇이 이동할 거리 n이 입력된다. (\(1 \le n \le 100,000\))
출력 설명
계단을 오를 수 있는 가지수에 100,003으로 나눈 나머지로 구하여라
입력 예시 Copy
3
출력 예시 Copy
4