30194번 - 징검다리 뒤로 건너기
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB | 85 | 55 | 47 | 72.308% |
문제
$1$번부터 $N$번까지 번호가 붙은 $N$개의 돌이 순서대로 일렬로 나열되어 있습니다. $1$번 돌에서 출발하여 $N$번 돌까지 주어진 정수 $K$에 대해 다음 규칙을 만족하면서 이동하려 합니다.
- $i$번 돌에서는 $1\le x\le K$인 정수 $x$에 대해 $i+x$번 돌로 이동하거나, $i-1$번 돌로 이동할 수 있습니다.
- 돌이 없는 위치로는 이동할 수 없습니다.
- 출발점과 도착점을 포함하여, 이미 밟은 돌은 다시 밟을 수 없습니다.
규칙에 따라 $1$번 돌에서 $N$번 돌까지 이동하는 경우의 수를 소수 $1\, 000\, 000\, 007(=10^9+7)$로 나눈 나머지를 구해봅시다. 밟은 돌의 번호를 순서대로 나열한 수열이 다르면 다른 이동으로 생각합니다.
입력
첫 번째 줄에 돌의 개수 $N$과 문제의 정수 $K$가 공백으로 구분되어 주어집니다. ($1\le N\le 2\, 000$; $1\le K\le 50$)
출력
첫 번째 줄에 규칙에 따라 $1$번 돌에서 $N$번 돌까지 이동하는 경우의 수를 $1\, 000\, 000\, 007(=10^9+7)$로 나눈 나머지를 출력합니다.
예제 입력 1
5 3
예제 출력 1
12
가능한 모든 경우는 다음과 같습니다.
- $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$
- $1 \rightarrow 2 \rightarrow 3 \rightarrow 5$
- $1 \rightarrow 2 \rightarrow 4 \rightarrow 5$
- $1 \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 5$
- $1 \rightarrow 2 \rightarrow 5$
- $1 \rightarrow 3 \rightarrow 2 \rightarrow 4 \rightarrow 5$
- $1 \rightarrow 3 \rightarrow 2 \rightarrow 5$
- $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$
- $1 \rightarrow 3 \rightarrow 5$
- $1 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 5$
- $1 \rightarrow 4 \rightarrow 3 \rightarrow 5$
- $1 \rightarrow 4 \rightarrow 5$
예제 입력 2
8 4
예제 출력 2
191
예제 입력 3
1923 45
예제 출력 3
703532137
출처
University > 서울대학교 > 서울대학교 프로그래밍 경시대회 > 2023 서울대학교 프로그래밍 경시대회 > Division 2 F번
- 문제를 만든 사람: 16silver
- 문제를 검수한 사람: azberjibiou, kdh9949, sharaelong, starwh03, whqkrkt04
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호