28243번 - 조별 수업
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 187 | 75 | 60 | 39.735% |
문제
송도고등학교의 박상진 선생님은 조별 수업에서 버스를 타는 학생은 없고 모두가 협력할 수 있는 획기적인 방법을 고안해내셨다!
박상진 선생님의 획기적인 방법을 사용하지 않은 보통의 조별 수업 상황이다.
그 방법은 바로 조를 특별한 방식으로 짜는 것이다.
$1$번부터 $n$번까지의 번호가 배정된 학생들 $n$명이 임의의 순서로 일렬로 서 있을 때, 이를 연속한 구간 여러 개로 나누어 조를 짠다. 이때 모든 구간에 대해 각 구간의 길이가 구간에 속한 학생들의 번호 중 최솟값과 같아야 올바른 조 짜기 방법이 된다.
박상진 선생님은 학생들이 일렬로 서 있을 수 있는 모든 경우에 대한 올바른 조 짜기 방법의 수의 합을 알고 싶다. 선생님을 도와 이를 구하는 프로그램을 작성하여라.
단, 답이 너무 커질 수 있으니 답을 $10^9+7$로 나눈 나머지를 출력한다.
입력
첫 번째 줄에 학생 수 $n$이 주어진다.
출력
학생들이 일렬로 서 있을 수 있는 모든 경우에 대한 올바른 조 짜기 방법의 수의 합을 $10^9+7$로 나눈 나머지를 출력하여라.
제한
- $1\le n\le 1\,000$.
예제 입력 1
3
예제 출력 1
4
학생들이 일렬로 서 있을 수 있는 모든 경우는 다음 $6$가지가 전부이다.
- $[1,2,3]$: $(1)(2\,3)$으로 조를 짤 수 있다.
- $[1,3,2]$: $(1)(3\,2)$로 조를 짤 수 있다.
- $[2,1,3]$: 조를 짤 수 없다.
- $[2,3,1]$: $(2\,3)(1)$로 조를 짤 수 있다.
- $[3,1,2]$: 조를 짤 수 없다.
- $[3,2,1]$: $(3\,2)(1)$로 조를 짤 수 있다.
따라서 학생들이 일렬로 서 있을 수 있는 모든 경우에 대한 올바른 조 짜기 방법의 수의 합은 $4$이다.
예제 입력 2
2
예제 출력 2
0
학생들이 일렬로 서 있을 수 있는 모든 경우는 다음 $2$가지가 전부이다.
- $[1,2]$: 조를 짤 수 없다.
- $[2,1]$: 조를 짤 수 없다.
따라서 학생들이 일렬로 서 있을 수 있는 어떤 경우에 대해서도 올바른 조 짜기 방법이 존재하지 않는다.
출처
School > 송도고등학교 > 송도고 코드마스터 2023 H번
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호