22880번 - 봉화대 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 343 | 220 | 191 | 71.269% |
문제
$N$개의 마을이 일렬로 1번부터 $N$번까지 순서대로 산등성이를 따라 있다. 각 마을의 높이는 1 이상 $N$ 이하의 자연수 중 하나이며 서로 다르다. 외침을 막기 위해 마을을 여러 구간으로 나누어, 각 구간의 가장 높은 마을에 봉화대를 설치하려 한다. 각 구간은 하나 이상의 연속된 마을을 포함해야 하고, 각 마을은 정확히 하나의 구간에 포함되어야 한다. 봉화대의 효율적인 상호 통신을 위해, 봉화대가 설치된 마을의 높이는 번호의 오름차순으로 봤을 때 증가해야 한다. 전략 도모를 위해 가능한 구간 배치의 개수를 파악해보고자 한다.
| 그림 H.1: 조건을 만족한 봉화대 설치 예시 | 그림 H.2: 조건을 만족하지 않은 봉화대 설치 예시 |
입력
첫째 줄에는 마을의 개수를 의미하는 정수 $N$이 주어진다. ($1 \leq N \leq 500\ 000$)
둘째 줄에는 각 마을의 높이를 의미하는 $N$개의 정수 $h_1, h_2, \cdots, h_N$이 공백으로 구분되어 주어진다. ($1 \leq h_i \leq N$)
$h_i$는 $i$번째 마을의 높이를 의미하며 서로 다르다.
출력
조건을 만족하며 $N$개의 마을을 구간으로 나누는 방법의 가짓수를 $1\ 000\ 000\ 007$로 나눈 나머지를 출력한다.
예제 입력 1
5 1 4 2 5 3
예제 출력 1
6
예제 입력 2
3 3 2 1
예제 출력 2
1
예제 입력 3
8 6 3 1 7 2 5 4 8
예제 출력 3
20
힌트
첫 번째 예제의 가능한 모든 배치는 (1 / 4 / 2 5 3), (1 / 4 2 / 5 3), (1 / 4 2 5 3), (1 4 / 2 5 3), (1 4 2 / 5 3), (1 4 2 5 3) 이다. /는 구간의 경계이며, 봉화대는 밑줄로 강조된 높이의 마을에 설치된다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호