연습문제
탑의 높이
- 난이도
- Lv. 4
- 제출
- 164 명
- 참가자
- 37 명
- 정답률
- 28.79 %
- 지원 언어
-
CC++JavaPythonRust
로그인 후 문제풀이가 가능합니다.
언어별 시간/메모리
언어 | 시간 | 메모리 |
---|---|---|
Java | 3초 | 1024MB |
Python | 3초 | 1024MB |
C | 2초 | 1024MB |
C++ | 2초 | 1024MB |
Rust | 2초 | 1024MB |
당신의 회사는 대륙간 통신을 처리하거나, 우주 엘리베이터의 건설 등에 이용할 수 있도록, 지상에서부터 높은 탑을 쌓았다. 이 탑은 총 개의 기둥이 일렬로 놓여 있는 형태이며, 왼쪽에서부터 번째 기둥의 높이는 이다.
탑의 안정성을 위해, 두 인접한 기둥의 높이 차이는 이하이다. 즉, 모든 에 대해, 이다.
탑의 높이는 가장 높은 기둥의 높이로 정의한다. 즉, 중 최댓값 (가장 큰 값)을 탑의 높이로 한다.
당신의 회사는 탑의 높이를 최대한 높이고 싶다. 탑을 새로 건설할 수는 없으므로, 각각의 기둥의 높이를 높일 수밖에 없다. 당신은 아래와 같은 연산을 최대 회 수행할 수 있다.
- 기둥 하나를 정해서, 높이를 증가시킨다.
탑은 높이를 높인 이후에도 안정성을 유지해야 하기 때문에, 항상 두 인접한 기둥의 높이 차이는 이하여야 한다.
최적의 연산을 통해 얻을 수 있는 탑의 최대 높이를 구하는 프로그램을 작성하라.
제약조건
[문제 제약 조건]
[조건 1] 주어지는 모든 수는 정수이다.
[조건 2]
[조건 3]
[조건 4] 모든 에 대해,
[서브 태스크별 제약 조건]
Subtask1 (10점): ,
Subtask2 (20점): ,
Subtask3 (30점):
Subtask4 (40점): 추가 제약 조건 없음
입력형식
첫 번째 줄에 두 정수 과 가 공백으로 구분되어 주어진다.
두 번째 줄에 개의 정수 이 공백으로 구분되어 주어진다.
출력형식
첫 번째 줄에 최대 높이를 출력한다.
입력예제1
5 4 2 2 2 2 2
출력예제1
4
아래와 같이 총 4번의 연산으로 높이를 로 만들 수 있다.
•2 2 2 2 2
•2 3 2 2 2
•2 3 3 2 2
•2 3 3 3 2
•2 3 4 3 2
입력예제2
7 10 1 2 3 4 3 2 1
출력예제2
6
입력예제3
8 12 1 2 3 4 3 2 1 2
출력예제3
7