마디 채우기
문제
악보를 쓰는 사람은 한 마디를 음표로 빈틈없이 채워야 한다. 지금 채워야 하는 마디의 길이는 N박이다.
쓸 수 있는 음표는 두 가지뿐이다. 하나는 1박을 차지하는 짧은 음표이고, 다른 하나는 2박을 차지하는 긴 음표다. 음표는 마디의 왼쪽 끝에서부터 차례로 늘어놓으며, 마지막 음표의 끝이 마디의 오른쪽 끝과 딱 맞아야 한다. 늘어놓은 음표의 순서가 다르면 서로 다른 마디로 센다.
결과적으로 마디의 길이 N이 주어졌을 때, 마디를 채우는 방법의 수를 구하는 프로그램을 작성하여라. 답이 매우 커질 수 있으므로 15,746으로 나눈 나머지를 출력한다.
예를 들어 N=4박인 마디를 채운다고 해보자. 짧은 음표를 1, 긴 음표를 2로 적으면 채우는 방법은 다음의 표와 같다.
| 방법 | 왼쪽부터 늘어놓은 음표 |
|---|---|
| 1 | 1, 1, 1, 1 |
| 2 | 1, 1, 2 |
| 3 | 1, 2, 1 |
| 4 | 2, 1, 1 |
| 5 | 2, 2 |
따라서 N=4일 때 정답은 5이다.
마디의 길이를 1박부터 6박까지 올려 가며 같은 방식으로 세면 다음과 같다.
| N | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 채우는 방법의 수 | 1 | 2 | 3 | 5 | 8 | 13 |
마디의 맨 오른쪽에 놓이는 음표를 생각해 보면 규칙이 보인다. 맨 오른쪽이 짧은 음표라면 그 왼쪽에 N-1박을 채운 셈이고, 맨 오른쪽이 긴 음표라면 그 왼쪽에 N-2박을 채운 셈이다. 두 경우는 겹치지 않으므로 N박을 채우는 방법의 수는 N-1박과 N-2박을 채우는 방법의 수를 더한 값이다.
마디가 길어지면 방법의 수가 아주 빠르게 늘어난다. 그러므로 셈을 끝까지 다 한 뒤에 나머지를 구하지 말고, 더해 가는 중간마다 15,746으로 나눈 나머지만 남겨 두고 가야 한다.
입출력 예시
예시 1
입력
4
출력
5
예시 2
입력
5
출력
8
예시 3
입력
1000000
출력
7871
입력 조건
가장 먼저 채워야 하는 마디의 길이 N이 자연수로 한 줄에 주어진다. (N은 1 이상 1,000,000 이하의 자연수다.) N은 박의 수를 뜻하므로 0이나 음수, 소수로는 주어지지 않는다. 입력은 이 한 줄로 끝나며, 다른 줄은 주어지지 않는다.
출력 조건
마디를 채우는 방법의 수를 15,746으로 나눈 나머지를 한 줄에 출력한다. 수 하나만 출력하므로 줄 끝에 남기는 공백은 없다.
요구사항
- 음표는 1박짜리와 2박짜리 두 가지뿐입니다
- 늘어놓은 순서가 다르면 서로 다른 방법으로 셉니다
- 마디에 빈틈이 남거나 마디를 넘어가면 안 됩니다
- N이 1이면 짧은 음표 하나뿐이므로 답은 1이고, N이 2이면 답은 2입니다
- 더해 가는 중간마다 15,746으로 나눈 나머지를 들고 가야 수가 넘치지 않습니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
4
5
5
8
1000000
7871
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.