Python 34제] 2021년 한국정보올림피아드 1차대회 중등부 2교시 1번:꿀따기

문제]

아래와 같이 좌우로 N개의 장소가 있다.

장소들 중 서로 다른 두 곳을 골라서 벌을 한 마리씩 둔다. 또, 다른 한 장소를 골라서 벌통을 둔다. 아래 그림에서 연한 회색의 장소는 벌이 있는 장소이고 진한 회색의 장소는 벌통이 있는 장소이다.

두 마리 벌은 벌통으로 똑바로 날아가면서 지나가는 모든 칸에서 꿀을 딴다. 각 장소에 적힌 숫자는 벌이 지나가면서 꿀을 딸 수 있는 양이다.

 

1. 두 마리가 모두 지나간 장소에서는 두 마리 모두 표시된 양 만큼의 꿀을 딴다.
   (벌통이 있는 장소에서도 같다.)
2. 벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다.

 

위의 그림과 같이 배치된 경우 두 마리의 벌 모두  4 + 1 + 4 + 9 + 9 = 27의 꿀을 따서, 전체 꿀의 양은 54 가 된다.

위의 그림과 같이 배치된 경우 왼쪽 장소에서 출발한 벌은 9 + 4 + 4 + 9 + 9 = 35의 꿀을 따고 오른쪽 장소에서 출발한 벌은 4 + 9 + 9 = 22의 꿀을 따므로, 전체 꿀의 양은 57이 된다.

위의 그림과 같은 경우는 전체 꿀의 양이 31이 된다.
장소들의 꿀 양을 입력으로 받아 벌들이 딸 수 있는 가능한 최대의 꿀의 양을 계산하는 프로그램을 작성하라.

 

제약조건

• 3 ≤ N ≤ 100 000
• 각 장소의 꿀의 양은 1 이상 10 000 이하의 정수이다.

 

입력 형식
첫 번째 줄에 장소의 수 N이 주어진다.
다음 줄에 왼쪽부터 각 장소에서 꿀을 딸 수 있는 양이 공백 하나씩을 사이에 두고 주어진다.

출력 형식
첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다.

 

표준 입력1

7

9 9 4 1 4 9 9

 

표준 출력1

57

 

표준 입력2

3

2 5 4

 

표준 출력2

10

 

 

 

출처 : 한국정보올림피아드(2021년도 한국정보올림피아드 1차 대회 중등부 2교시 문제)

 

 

참고풀이]

import sys #exit()

n = int(input())
if 3<=n<=100000:
    a = list(map(int,input().split()))
    for b in a:
        if 1<=b<=10000:
            continue
        else:
            sys.exit()
else:
    sys.exit()
    
#Process Part
s=[]
s.append(a[0])
Sum=0
for i in range(1,n):
    s.append(s[i-1]+a[i])

#양쪽 끝방에 벌이 있고, 꿀통이 임의의 방에 있을 경우
for i in range(1,n-1):
    Sum=max(Sum,s[n-2]-a[0]+a[i])
    
#0번방에 벌한마리, 임의의 방에 벌, 그리고 끝방에 꿀통이 있을 경우
for i in range(1,n-1):
    Sum=max(Sum,s[i-1]-a[0]+2*(s[n-1]-s[i]))
    
#n-1방에 벌한마리 그리고 임의의 방에 벌, 꿀통도 임의의 방에 있을 경우
for i in range(1,n-1):
    Sum=max(Sum,2*s[i-1]+s[n-2]-s[i])

#결과출력
print(Sum)

 

 

참고풀이 결과]

 

 

 

대한민국의 아름다운 영토, 독도의 봄