1988번 - 낮잠 시간 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 345 | 113 | 92 | 42.791% |
문제
동혁이는 낮잠 시간을 N개의 구간으로 나누어서 그 중 B개의 구간동안만 잠을 자려고 한다. B개의 구간이 연속일 필요는 없다. 각 구간동안에 동혁이가 얻을 수 있는 피로 회복량이 정해져 있는데, 동혁이는 이 양을 최대화 하려고 한다. 잠을 설치는 경우가 한 예이다.
예를 들어 구간을 5개로 나누었을 경우, B=3이고 [2 3 4]구간에 잠을 자기로 했다고 치자. 잠을 들기 위해서는 준비 시간이 필요하기 때문에 이 준비 시간 동안에는 피로 회복이 되지 않는다. 각 분할의 첫 구간에서는 피로가 회복되지 않는 것이다. 따라서 [2 3 4] 구간에 잠을 자면 [2]구간에서는 회복을 못하고 [3 4]구간에서만 회복할 수 있다. 이 구간은 N번째 구간과 1번째 구간이 이어져있지 않다고 생각하자.
동혁이가 어떻게 하면 피로회복을 최대로 할 수 있는지 구해보자.
입력
첫 줄에 두 정수 N과 B가 주어진다. N은 3 이상 3,000 이하, B는 2 이상 N 이하이다. 다음으로 N줄에 걸쳐 피로회복량이 주어지고, 이 값은 0 이상 200,000 이하의 정수이다.
출력
첫 줄에 가능한 최대 피로회복량을 출력한다.
예제 입력 1
5 3 0 3 1 4 2
예제 출력 1
6
힌트
가령 [1] [4 5]와 같이 선택한다면 0 + 0 + 2 가 된다. (구간을 여러 분할하면 여러 분할의 각 첫 구간은 피로 회복을 할 수 없다) 위의 예에서는 [3 5]구간을 선택하면 0 + 4 + 2 가 되어 최대가 된다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호