1844번 - 농지 정리 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 38 | 7 | 5 | 71.429% |
문제
N미터의 긴 1차원 농지가 있다. 각각의 지역에는 그 지역의 높이가 주어져 있다. 그리고 높이가 같은 한 개 이상의 연속된 구간의 높이가, 양 옆의 높이보다 높을 경우 그 구간을 봉우리라고 부른다.
만약에 높이가 1, 2, 3, 3, 3, 2, 1, 3, 2, 2, 1, 2로 주어진 농지가 있다면 아래 그림과 같이 되어 봉우리의 수는 3개가 된다.
* * * *
* * * * * * * * *
* * * * * * * * * * * *
1 2 3 3 3 2 1 3 2 2 1 2
그런데 봉우리가 너무 많을 경우에는 농지에서 농작물을 경작하기가 힘들기 때문에 몇 개의 지역을 깎아서 봉우리의 수를 K개 이하로 줄이려 한다. 위의 그림에서 아래와 같이 5 개의 *을 잘라내면 봉우리의 개수는 1개로 줄어들게 된다.
* * * -
* * * * * - - - -
* * * * * * * * * * * *
1 2 3 3 3 2 1 1 1 1 1 1
땅을 깎는 데에는 매우 많은 비용이 드므로 땅을 깎는 비용을 최소화하려고 한다. 즉 위와 같이 *로 그림을 표현하였을 때, 잘라내는 *의 개수를 최소화 한다는 것이다. 농지의 높이 정보와 K가 주어져 있을 때, 최소로 깎아내는 *의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 농지의 길이 N(1 ≤ N ≤ 1,000)과 K(1 ≤ K ≤ 25) 가 주어진다. 그리고 두 번째 줄부터 N+1번째 줄까지 농지의 높이 h(1 ≤ h ≤ 1,000,000)가 주어진다.
출력
첫 줄에 최소로 깎아내는 *의 개수를 출력한다.
예제 입력 1
12 1 1 2 3 3 3 2 1 3 2 2 1 2
예제 출력 1
5
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호