2102번 - 보석 줍기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 487 | 107 | 73 | 23.548% |
문제
수영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1 ≤ N ≤ 100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 수영이는 가급적 많은 이득을 얻을 수 있도록 보석을 가져가려 한다. 이때, 다음 세 가지의 조건이 만족되어야 한다.
- 보석들과 함께 함정이 설치되어 있기 때문에 1번 보석이 놓여있는 곳부터, N번 보석이 놓여 있는 곳까지 순서대로 이동해야 한다. 물론 1번 보석부터 N번 보석까지가 차례로 놓여있다고 가정하며, 보석을 줍다가 도중에 뒤로 돌아갈 수 없는 것이다. 각각의 보석이 놓여 있는 위치에서 수영이는 두 가지 선택을 할 수 있는데, 그 자리에 있는 보석을 줍거나 줍지 않고 그 다음 보석이 놓여 있는 곳으로 이동하게 된다.
- 또한 보석들과 함께 경보 장치가 설치되어 있는데, 이 장치는 보석을 한 개 주우면 작동하게 된다. 보석을 한 개 더 줍게 되면 이 경보 장치는 유적을 무너뜨리도록 설계되어 있다. 단, 경보 장치를 속일 수 있는 방법이 있는데, M(1 ≤ M ≤ N)개 이상의 연속적인 보석을 줍게 되면 경보 장치가 인식하지 못하게 된다. 따라서 보석을 줍기 시작하면 그 위치에 있는 보석을 포함하여 M개 이상의 보석을 연속적으로 주워야 하고, 줍기를 멈춘 후에는 다시 줍기 시작할 수 없다. 즉, 보석을 주울 기회는 오직 한 번 뿐이며, 보석을 주울 때에는 연속적으로 M개 이상 주워야 한다.
- 주운 보석들의 가치의 합이 크더라도, 보석의 개수가 많다면 무게가 많이 나가서 힘들 수도 있다. 물론, 보석들의 가치의 합이 충분히 크다면 무거움을 감수할 수도 있다. 따라서 수영이는 주운 보석들의 가치의 평균이 최대가 되도록 하려 한다.
보석들의 개수가 매우 많기 때문에, 수영이는 이 문제를 컴퓨터를 이용하여 풀기로 하였다. 보석들에 대한 정보가 주어졌을 때, 위의 조건들을 만족하면서 보석을 주울 때, 가치의 평균의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 차례로 각 보석의 가치가 주어진다. 각 보석의 가치는 0 이상 2,000 이하의 정수이다.
출력
첫째 줄에 가치의 평균의 최댓값을 1,000배 한 정수를 출력한다. 반올림 문제가 생길 수 있으므로, 정수 연산을 하여 1,000×(가치의 총 합)/(보석의 개수)을 출력하도록 한다.
예제 입력 1
10 6 6 4 2 10 3 8 5 9 4 1
예제 출력 1
6500
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호