16238번 - 독수리 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 328 | 196 | 145 | 58.000% |
문제
독수리는 양을 먹으면서 살고 있다. 양이 사는 곳은 크기가 1×N인 직사각형으로 나타낼 수 있고, 1×1 크기의 칸으로 나누어져 있다. 칸은 왼쪽에서부터 1번, 2번, ..., N번으로 번호가 매겨져 있다. i번 칸에 사는 양의 수는 Ai마리이다.
독수리는 매일 아침 양을 먹으러 간다. 1번 칸의 왼쪽이나 N번 칸의 오른쪽에서 날기 시작해 먹으려고 하는 양이 있는 칸까지 날아간다. 독수리는 칸을 벗어나서 날 수 없다. 먹으려고 하는 양이 있는 곳이 x번이라면, x번까지 날아간 다음, x번 칸에 있는 양을 모두 먹는다. 독수리는 하루에 한 칸에 있는 양만 먹을 수 있다.
양은 독수리를 매우 무서워하기 때문에, 독수리가 나는 모습을 보면 도망간다. 양은 칸의 위에 독수리가 나는 것을 확인하면 도망간다. 양이 도망가면, 그 칸에 있는 양의 수는 0마리가 된다. 예를 들어, 1번 칸의 왼쪽에서 날기 시작해서 x번 칸에 도착했다면, 1번부터 x-1번 칸까지에 있던 양이 모두 도망가 0마리가 된다. N번 칸의 오른쪽에서 날기 시작했다면, x+1번칸 부터 N번 칸까지에 있던 양이 모두 도망간다.
또한, 이곳은 위험한 곳이기 때문에, 매일 밤에 모든 칸에 있던 양의 수가 1마리씩 줄어든다.
독수리가 매일 매일 어떤 칸에 있는 양을 먹는지와 어느 쪽에서부터 날기 시작하는지에 따라 먹을 수 있는 양의 수가 달라진다.
양의 수가 주어졌을 때, 독수리가 먹을 수 있는 양의 수의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 칸의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)
둘째 줄에 각 칸에 있는 양의 수 A1, A2, .., AN이 주어진다. (0 ≤ Ai ≤ 100,000)
출력
첫째 줄에 독수리가 먹을 수 있는 양의 최대 수를 출력한다.
예제 입력 1
5 1 10 4 10 1
예제 출력 1
21
첫째 날 1번 칸의 왼쪽에서 날기 시작해 2번 칸의 양을 먹는다. 독수리가 먹은 양의 수는 10마리이다. 2번 칸에 있는 양을 먹었기 때문에, 1번, 2번 칸의 양의 수는 0이 된다. 첫째 날의 밤에 양의 수는 1씩 감소해 A1 = 0, A2 = 0, A3 = 3, A4 = 9, A5 = 0 이 된다.
둘째 날에는 N번 칸의 오른쪽에서 날기 시작해 4번 칸의 양을 먹는다. 이제 독수리가 먹은 양의 수는 19마리가 된다. 양의 수가 1씩 감소한 후 양의 수는 A1 = 0, A2 = 0, A3 = 2, A4 = 0, A5 = 0 이 된다.
셋째 날에 3번 칸에 있는 양을 먹어 총 21마리의 양을 먹을 수 있다.
정답이 나올 수 있는 방법은 위에서 설명한 방법 이외에도 여러가지 방법이 있을 수 있다.
예제 입력 2
5 1 1 1 1 1
예제 출력 2
1
예제 입력 3
6 10 1 1 1 1 10
예제 출력 3
19
예제 입력 4
7 1 2 3 4 5 6 7
예제 출력 4
16
예제 입력 5
14 10 1 10 2 10 3 10 4 10 3 10 2 10 1
예제 출력 5
49
예제 입력 6
4 0 0 0 0
예제 출력 6
0
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호