Greedy_15_꿀따기(21758)
Greedy15꿀따기(21758)
문제
아래와 같이 좌우로 개의 장소가 있다.
아래와 같이 좌우로 개의 장소가 있다.
장소들 중 서로 다른 두 곳을 골라서 벌을 한 마리씩 둔다. 또, 다른 한 장소를 골라서 벌통을 둔다. 아래 그림에서 연한 회색의 장소는 벌이 있는 장소이고 진한 회색의 장소는 벌통이 있는 장소이다.
두 마리 벌은 벌통으로 똑바로 날아가면서 지나가는 모든 칸에서 꿀을 딴다. 각 장소에 적힌 숫자는 벌이 지나가면서 꿀을 딸 수 있는 양이다.
두 마리가 모두 지나간 장소에서는 두 마리 모두 표시된 양 만큼의 꿀을 딴다. (벌통이 있는 장소에서도 같다.)
벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다.
위의 그림과 같이 배치된 경우 두 마리의 벌 모두 의 꿀을 따서, 전체 꿀의 양은 54가 된다.
위의 그림과 같이 배치된 경우 왼쪽 장소에서 출발한 벌은 의 꿀을 따고 오른쪽 장소에서 출발한 벌은 의 꿀을 따므로, 전체 꿀의 양은 이 된다.
위의 그림과 같은 경우는 전체 꿀의 양이 31이 된다.
장소들의 꿀 양을 입력으로 받아 벌들이 딸 수 있는 가능한 최대의 꿀의 양을 계산하는 프로그램을 작성하라.
입력
첫 번째 줄에 장소의 수 이 주어진다.
다음 줄에 왼쪽부터 각 장소에서 꿀을 딸 수 있는 양이 공백 하나씩을 사이에 두고 주어진다.
출력
첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다.
풀이
- 두 꿀벌의 위치와 벌통의 위치를 3가지로 나눠 각 경우중 가장 큰 값 출력
- 벌통이 오른쪽 끝에 있는경우
- 벌통이 왼쪽 끝에 있는경우
- 벌통이 두 벌 사이에 있는 경우
코드
import sys
sys.stdin = open("input.txt","rt")
def input():
return sys.stdin.readline().rstrip()
n = int(input())
ans=0
a = list(map(int,input().split()))
s=[]
s.append(a[0])
for i in range(1,n):
s.append(s[i-1]+a[i])
# s라는 배열에 각 자리에 누적 합을 구한다.
for i in range(1,n-1):
ans=max(ans,s[n-2]-a[0]+a[i])
# 꿀이 맨 오른쪽에 위치했을 경우 가장 큰 값을 계산한다.
for i in range(1, n - 2):
ans = max(ans, s[n-1] - a[0] - a[i] + s[n-1] - s[i])
# 꿀이 맨 오른쪽에 위치했을 경우 가장 큰 값을 계산한다.
for i in range(1,n-1):
ans=max(ans,2*s[i-1]+s[n-2]-s[i])
print(ans)
# 꿀이 사이에 있는 경우 가장 큰 값을 계산한다.
print(ans)
배운 것
코멘트
Author And Source
이 문제에 관하여(Greedy_15_꿀따기(21758)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@angel_eugnen/Greedy15꿀따기21758저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)