이번에 경곽이는 수력발전에 대해서 배우고, 주어진 환경에서 최대한 효과를 볼 수 있도록 수력발전소위치를 선정하고자 한다. 수력발전소의 효율은 수력발전소가 설치된 영역 내부의 각 영역의 높이차가 클수록 높다. 만약 수력발전소의 크기가 5 이고, 발전소가 위치한 5군데 영역의 높이의 최댓값과 최솟값의 차이가 그 발전소의 발전량이 된다. 길이가 n인 강이 주어진다. 강의 각 영역에 원하는 만큼의 수의 발전소를 원하는 크기로 설치할 수 있다. 예를 들어 강의 길이가 6 이고, 강의 각 영역의 높이가 다음과 같다면, 2 1 2 3 1 2 크기가 2인 발전소 2개를 다음과 같이 설치한다고 가정하자. 2 [ 1, 2 ] [ 3, 1 ] 2 빨간색 발전소의 발전량은 최댓값 2 최솟값 1이므로 발전량은 1이다. 파란색 발전소의 발전량은 최댓값 3 최솟값 1이므로 발전량은 2이다. 따라서 전체 발전량은 3이 된다. 물론 다음과 같이 발전량이 3인 경우도 만들 수 있다. 2 [ 1 2 3 ] [ 1 2 ] 이 경우에는 크기가 3인 발전소 1개와 크기가 2인 발전소 1개를 만든 것이다. 이 때 크기가 3인 발전소의 발전량은 2, 크기가 2인 발전소의 발전량은 1 이므로 전체 발전량은 3이다. 하지만 어떤 방법으로 발전소를 건설하더라도 3보다 더 많은 양의 발전소를 설치할 수는 없다. 따라서 주어진 강에서는 최대 3의 전기를 생산할 수 있다. 강의 크기와 강의 각 영역의 높이값이 주어질 때 최대 발전량을 구하는 프로그램을 작성하시오.

수력발전소 (L)

문제 설명

입력

출력

예제

코드 제출

로그인

LOGIN