문제
아래와 같이 좌우로 N개의 장소가 있다.
장소들 중 서로 다른 두 곳을 골라서 벌을 한 마리씩 둔다. 또, 다른 한 장소를 골라서 벌통을 둔다. 아래 그림에서 연한 회색의 장소는 벌이 있는 장소이고 진한 회색의 장소는 벌통이 있는 장소이다.
두 마리 벌은 벌통으로 똑바로 날아가면서 지나가는 모든 칸에서 꿀을 딴다. 각 장소에 적힌 숫자는 벌이 지나가면서 꿀을 딸 수 있는 양이다.
- 두 마리가 모두 지나간 장소에서는 두 마리 모두 표시된 양 만큼의 꿀을 딴다. (벌통이 있는 장소에서도 같다.)
- 벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다.
위의 그림과 같이 배치된 경우 두 마리의 벌 모두 4+1+4+9+9=27의 꿀을 따서, 전체 꿀의 양은 54가 된다.
위의 그림과 같이 배치된 경우 왼쪽 장소에서 출발한 벌은 9+4+4+9+9=35의 꿀을 따고 오른쪽 장소에서 출발한 벌은 4+9+9=22의 꿀을 따므로, 전체 꿀의 양은 57이 된다.
위의 그림과 같은 경우는 전체 꿀의 양이 31이 된다.
장소들의 꿀 양을 입력으로 받아 벌들이 딸 수 있는 가능한 최대의 꿀의 양을 계산하는 프로그램을 작성하라.
입력
첫 번째 줄에 장소의 수 N이 주어진다.
다음 줄에 왼쪽부터 각 장소에서 꿀을 딸 수 있는 양이 공백 하나씩을 사이에 두고 주어진다.
출력
첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다.
제한
- 3≤N≤100 000
- 각 장소의 꿀의 양은 1 이상 10 000 이하의 정수이다.
서브태스크
| 1 | 11 | N≤20 |
| 2 | 13 | N≤500 |
| 3 | 31 | N≤5 000 |
| 4 | 45 | 추가적인 제한이 없음. |
예제 입력 1 복사
7
9 9 4 1 4 9 9
예제 출력 1 복사
57
예제 입력 2 복사
7
4 4 9 1 9 4 4
예제 출력 2 복사
54
예제 입력 3 복사
3
2 5 4
예제 출력 3 복사
10
[문제 풀이]
꿀통이 위치할 수 있는 경우는 3가지다
1. 가장 왼쪽에 위치하는 경우
- 이 경우 한 마리의 벌은 가장 오른쪽에 위치하고, 다른 한 마리는 꿀통과 다른 벌 사이에 위치한다
2. 가장 오른쪽에 위치하는 경우
- 이 경우 한 마리의 벌은 가장 왼쪽에 위치하고, 다른 한 마리는 꿀통과 다른 벌 사이에 위치한다.
3. 벌 사이에 위치하는 경우
- 이 경우는 가장 왼쪽과 가장 오른쪽에 벌이 한 마리씩 위치하고, 꿀통은 이 벌들 사이에 위치한다.
이 세 가지의 경우를 모두 따져서 가장 최대가 될 때의 값을 출력해야 한다.
sum []
- sum 리스트는 i번째까지의 원소의 누적합을 저장하는 리스트다.
예를 들어
[3, 5, 7, 4, 2]
라는 리스트가 있을 때
이 리스트의 sum 리스트는
3 (3+5) (3+5+7) (3+5+7+4) (3+5+7+4+2) -> [3, 8, 15, 19, 21]
가 된다.
case1
벌통이 가장 왼쪽에 위치할 때 벌 한 마리의 위치는 가장 오른쪽으로 결정되므로, 나머지 벌의 위치만 찾아주면 된다.
<벌 1이 따는 꿀의 양>
+ sum [n-2]
: 가장 오른쪽에 벌이 위치하기 때문에 마지막 원소를 제외한 합이다.
- data [i]
: i번째에 또 다른 벌이 위치한다면 이곳의 꿀도 딸 수 없다.
<벌 2가 따는 꿀의 양>
+ sum [i-1]
: 벌이 i번째에 위치한다면 이 벌은 i, i+1, i.... n-1까지의 꿀을 딸 수 없으므로 sum [i-1]을 더해준다
#case1 - left
for i in range(1,n-1):
ans=max(ans,sum[n-2]+sum[i-1]-data[i])
#왼쪽 끝에 벌통
#오른쪽 끝에 벌1, i번쨰 위치에 벌2
case 2
벌통이 가장 오른쪽에 위치할 때 벌 한 마리의 위치는 가장 왼쪽으로 결정되므로, 나머지 벌의 위치만 찾아주면 된다.
<벌 1이 따는 꿀의 양>
+ sum [n-1]
: 가장 왼쪽에 벌이 위치하기 때문에 일단 모든 원소를 합한다.
- data [0]
: 가장 왼쪽, 즉 0번째에 이 벌이 위치하기 때문에 꿀을 딸 수 없다.
- data [i]
: 또 다른 벌이 i번째에 위치한다면 꿀을 딸 수 없기 때문에 빼준다.
<벌 2가 따는 꿀의 양>
sum [n-1] - sum [i]
: 벌이 i번째에 위치한다면 i, i+1, i+2.... n-1까지 꿀을 딸 수 있다. 따라서 처음부터 끝까지 더한 값에서 처음부터 i까지 더한 값을 빼준다.
#case2 - right
for i in range(1, n-1):
ans = max(ans, sum[n-1] - data[0] - data[i] + sum[n-1] - sum[i])
#오른쪽 끝에 벌통
#왼쪽 끝에 벌1, i번째 위치에 벌2
case 3
두 마리의 벌은 각각 왼쪽 끝과 오른쪽 끝에 위치하며 벌통의 위치인 i만 찾아주면 된다.
벌통이 중간에 위치하기 때문에 중복해서 딸 수 있는 꿀은 벌통 위치에 존재하는 꿀뿐이다.
따라서
+sum [n-2] - data [0] 하여 좌우 끝 원소를 제외하고, 꿀통의 위치인 i번째 꿀만 한 번 더 더해준다.
#case3 - middle
for i in range(1,n-1):
ans=max(ans,sum[n-2] - data[0] + data[i])
#왼쪽 끝에 벌1, 오른쪽 끝에 벌2
#i번째 위치에 벌통
[전체 소스 코드]
import sys
input = sys.stdin.readline
n = int(input())
data = list(map(int,input().split()))
#최대값 저장 변수
ans=0
#i번째 원소까지의 누적합
sum=[]
sum.append(data[0])
for i in range(1,n):
sum.append(sum[i-1]+data[i])
#case1 - left
for i in range(1,n-1):
ans=max(ans,sum[n-2]+sum[i-1]-data[i])
#왼쪽 끝에 벌통
#오른쪽 끝에 벌1, i번쨰 위치에 벌2
#case2 - right
for i in range(1, n-1):
ans = max(ans, sum[n-1] - data[0] - data[i] + sum[n-1] - sum[i])
#오른쪽 끝에 벌통
#왼쪽 끝에 벌1, i번째 위치에 벌2
#case3 - middle
for i in range(1,n-1):
ans=max(ans,sum[n-2] - data[0] + data[i])
#왼쪽 끝에 벌1, 오른쪽 끝에 벌2
#i번째 위치에 벌통
print(ans)'알고리즘 > python' 카테고리의 다른 글
| [python/파이썬] 백준 11000 강의실 배정 (0) | 2022.03.24 |
|---|---|
| [python/파이썬] 백준 13164 행복 유치원 (0) | 2022.03.23 |
| [python/파이썬] 백준 21314 민겸수 (0) | 2022.03.21 |
| [python/파이썬] 백준 16953 A → B (0) | 2022.03.19 |
| [python/파이썬] 백준 20365 블로그2 (0) | 2022.03.17 |
