31537번 - 출근하기 싫어 1 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 199 | 88 | 76 | 46.626% |
문제
이 문제는 출근하기 싫어 2와 굵은 글씨로 적힌 부분과 제한 조건만 다릅니다.
누구나 그렇듯 동우는 출근하기 싫다. 그래도 출근해야 한다.
동우가 다니는 회사는 신기한 회사이다. 총 $N$명의 직원이 있는데, 이 중 최대 $1$명이 출근하지 않아도 업무를 정상적으로 진행할 수 있다. 하지만 $1$명보다 많이 출근하지 않으면 업무를 정상적으로 진행할 수 없다.
동우는 회사의 업무가 정상적으로 진행되는 것이 신기해 현재 시각으로부터 최근 $M$시간 동안 $N$명의 직원 각각이 총 몇 시간씩 출근했는지 살펴보았다.
직원들은 모두 정각에만 출근해 정각에만 퇴근하며, 한 사람이 여러 번 출근 혹은 퇴근할 수 있다. 최근 $M$시간 동안 업무를 계속 정상적으로 진행할 수 있도록 하는, $N$명의 직원이 출근한 조합의 경우의 수를 구하시오.
이때, $M$시간에 대해 매시 30분을 기준으로 출근해 있는 직원들의 목록이 한 번이라도 다른 경우 서로 다른 조합으로 간주한다. 현재는 정각이라 가정한다.
입력
첫 번째 줄에 직원의 수 $N$과 동우가 살펴본 최근 시간의 길이를 나타내는 정수 $M$이 공백으로 구분되어 주어진다. $(1\le N, M\le 10^6)$
두 번째 줄에 $N$명의 직원이 최근 $M$시간 동안 출근한 시간 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(0\le A_i \le M)$
출력
직원이 출근한 조합으로 가능한 경우의 수를 $10^9+7$로 나눈 나머지를 출력한다.
단, $10^9+7$은 소수이다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 21 | $N\times M \le 20$ |
| 2 | 24 | $N, M \le 6$ |
| 3 | 64 | $N, M \le 1000$ |
| 4 | 71 | 추가적인 제한 조건 없음 |
예제 입력 1
2 4 2 2
예제 출력 1
6
예제 입력 2
2 4 3 3
예제 출력 2
12
예제 입력 3
3 4 4 3 3
예제 출력 3
12
예제 입력 4
3 5 3 3 3
예제 출력 4
0
예제 입력 5
3 5 4 3 4
예제 출력 5
60
예제 입력 6
2 10 5 7
예제 출력 6
2520
출처
University > 고려대학교 > MatKor Cup > 제4회 고려대학교 MatKor Cup: 2024 Winter/Spring E번
- 문제를 만든 사람: eoaud0108, kidw0124, sshs29hanul
- 문제를 번역한 사람: tikiliki0417
- 문제를 검수한 사람: changhw, coo001, finimage, lighter, tlsdydaud1, utilforever, w8385, yijw0930
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호