10129번 - 작은 새 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 256 MB | 751 | 321 | 209 | 40.820% |
문제
경기과학고의 뒤뜰에는 일렬로 된 n개의 나무로 이루어진 숲이 있다. 그 중 첫 번째 나무 위에는 마지막 나무의 위로 올라가고 싶어하는 작은 새가 한 마리 있다. 그 새는 몸집이 매우 작기 때문에 한 번의 비행으로 날아갈 수 있는 거리에 한계가 있다. 만약 새가 i번째 나무 위에 있다면, 이 새는 한 번의 비행으로 i+1, i+2, …, i+k번째 나무 중 하나로 갈 수 있으며 그보다 멀리 떨어진 나무로는 가지 못한다.
또한, 작은 새에게 지금 있는 나무보다 높은 나무로 올라가는 일은 낮은 나무로 내려가는 일보다 더 힘든 일이다. 작은 새는 자기가 현재 위치한 나무보다 같거나 높은 높이의 나무로 날아가면 피로감을 느낀다고 한다.
작은 새의 목표는 자신이 피로감을 느끼는 횟수를 최소화하면서 마지막 나무에 도달하는 것이다. 또한, 이 작은 새에게는 똑같이 최소한의 피로로 마지막 나무로 가고 싶어 하는 친구 새들이 있으며 이들의 k값은 서로 다를 수 있다. 작은 새와 친구 새들이 그들의 목표를 달성할 수 있도록 도와주자.
입력
첫 번째 줄에는 나무의 수를 나타내는 정수 n (2 ≤ n ≤ 1,000,000)이 주어진다.
다음 줄에는 n개의 정수 d1, d2, …, dn (1 ≤ di ≤ 109) 가 주어진다. di는 i번째 나무의 높이를 의미한다.
세 번째 줄에는 마지막 나무로 날아가고 싶어하는 새의 수 q (1 ≤ q ≤ 25)가 주어진다.
다음 q개 줄 중 i번째 줄에는 i번째 새가 한 번의 비행으로 날아갈 수 있는 거리인 ki (1 ≤ ki ≤ n-1)가 주어진다.
출력
당신의 프로그램은 q줄에 걸쳐 답을 출력해야 한다. 출력의 i번째 줄에는 i번째 새가 마지막 나무에 도달할 때까지 피로감을 느끼는 횟수의 최솟값을 출력해야 한다.
예제 입력 1
9 4 6 3 6 3 7 2 6 5 2 2 5
예제 출력 1
2 1
힌트
예제의 첫 번째 새는 1, 3, 5, 7, 8, 9번 나무를 거쳐 간다. 이 새는 3번째 나무에서 5번째 나무로 갈 때와 7번째 나무에서 8번째 나무로 갈 때, 총 두 번 피로감을 느낀다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호