7984번 - 두더지 잡기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 167 | 35 | 20 | 20.833% |
문제
요즘 이상한 뉴스가 너무 많아서 그런지, 재현이의 성격은 점점 반사회적이고 폭력적으로 변했다. 얼마 전, 재현 이는 결국 학교의 3D 프린터를 사용해서 모형 권총을 프린트하고, 혼자 이상한 게임을 하기 시작했다.
재현이는 많은 두더지굴이 있는 잔디밭에서 게임을 시작했다. 잔디밭에는 n개의 두더지굴이 있으며, 두더지굴은 1번부터 n번까지 순서대로 번호가 부여되어 있다. 원형으로 늘어져 있으니, 1번 굴과 2번 굴, 2번 굴과 3번 굴, ..., n번 굴과 1번 굴은 인접해 있다.
현재 각각의 굴에는 ai 마리의 두더지가 있고, 재현이는 모형 권총으로 이들을 쫓아낼 계획이다. 재현이가 모형 권총을 쏴서 i번 굴에 있는 두더지에게 겁을 주면, 그 굴에 있는 두더지들이 겁을 먹고 도망가게 된다. (모형이라 죽지는 않는다.) 뿐만 아니라, 그 굴과 인접한 양 옆 두개의 굴에 있는 두더지들도 겁을 먹어서, 인접한 굴로 이동하게 된다. 당연히, 인접한 굴이라 하면 i번 굴은 아니다.
예를 들어, 10번 굴에 겁을 줬다면, 10번 굴에 있는 두더지는 모두 굴을 탈출하고, 9번 굴에 있는 두더지는 8번 굴로 도망가고, 11번 굴에 있는 두더지는 12번 굴로 도망간다.
재현이는 3D 프린터로 k개의 총알을 만들었고, 최대한 많은 두더지를 쫓아내고 싶다. 총을 k번 이하로 사용했을 때, 최대 몇 마리의 두더지가 굴을 탈출하는가?
입력
첫 번째 줄에 두더지굴의 수 n, 총의 최대 사용 가능 수 k가 주어진다. (5 ≤ n ≤ 2000, 1 ≤ k ≤ n)
이후 n개의 정수 a1, a2, ..., an가 주어진다. (0 ≤ ai ≤ 106) i번째 굴에 ai마리의 두더지가 산다는 것을 의미한다.
출력
총을 k번 이하로 사용했을 때, 탈출시킬 수 있는 두더지 수의 최댓값을 출력한다.
예제 입력 1
5 2 6 1 5 3 4
예제 출력 1
13
힌트
초기 두더지 굴의 상태는 [6, 1, 5, 3, 4] 이다.
첫 번째로, 재현이는 1번째 굴에 총을 쏴서, 6마리의 두더지를 탈출시킨다. 두더지 굴의 상태는 [0, 0, 6, 7, 0]이 된다.
이제, 재현이는 4번째 굴에 총을 쏴서, 7마리의 두더지를 탈출시킨다. 총 13마리가 탈출한다.
출처
ICPC > Regionals > Europe > Central European Regional Contest > Poland Collegiate Programming Contest > AMPPZ 2012 K번
High School > 경기과학고등학교 > 나는코더다 2016 송년대회 H번
- 문제를 번역한 사람: koosaga
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호