문제
"jungol 1141 불쾌한 날"의 소들이 불쌍하다고 느낀 정원이는 일정 구간의 소들의 위치를 역순으로 바꾸어 불쾌한 정도를 줄여보고자 한다.
그런데 소들의 위치를 역순으로 바꾸는 일은 쉽지 않은 일이어서 한 번만 할 생각이다.
위치를 역순으로 바꾸어도 소들의 보는 방향을 여전히 동쪽이다.
어느 구간을 바꾸어야 소들이 볼 수 있는 머리 모양의 수의 총합을 최소로 할 수 있을까?
그 수를 최소로 할 때 그 합을 출력하는 프로그램을 작성하시오.
아래 그림과 같은 예제라면 1번 ~ 4번 소의 위치를 역순으로 바꾸면 4(2), 3(4), 2(2), 1(5), 5(6), 6(1) 이 된다.
이때 소들이 볼 수 있는 머리 모양의 수의 총합은 0 + 1 + 0 + 0 + 1 + 0 = 2로 최소가 된다.
임의의 한 구간을 뒤집어 i번 소들이 볼 수 있는 머리 모양의 수를 Ci 이라고 할 때,
C1부터 CN까지의 합이 최소가 되는 값을 구하여 출력하는 프로그램을 작성하시오.
입력
입력은 두 줄로 이뤄지며 입력의 첫 번째 줄에는 N 이 입력된다. ( 2 <= N <= 1,000) 그리고 그 다음 줄에는 N 개의 숫자가 주어지며, 각 i번째 소의 키를 뜻한다.
소의 키 h는 ( 1 <= h <= 1,000,000,000)이다.
출력
임의의 한 구간 s ~ e( 1 <= s < e <= N)를 뒤집어 i번 소들이 볼 수 있는 머리 모양의 수를 Ci 이라고 할 때, C1부터 CN 까지의 합이 최소가 되는 값을 구하여 출력하시오.
예제
6
5 2 4 2 6 1
2
출처
comkiwer
로그인해야 코드를 작성할 수 있어요.