21758번 꿀 따기 파이썬

문제

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

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

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

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

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

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

위의 그림과 같은 경우는 전체 꿀의 양이 31이 된다.

장소들의 꿀 양을 입력으로 받아 벌들이 딸 수 있는 가능한 최대의 꿀의 양을 계산하는 프로그램을 작성하라.

입력

첫 번째 줄에 장소의 수 N이 주어진다.

다음 줄에 왼쪽부터 각 장소에서 꿀을 딸 수 있는 양이 공백 하나씩을 사이에 두고 주어진다.

출력

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

제한

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

55점

T = int(input())
S = list(map(int,input().split()))

#벌벌꿀
#꿀벌벌
#벌꿀벌
maxv = 0

#벌벌꿀
for i in range(1,T):
    first = sum(S[1:])-S[i]
    second = sum(S[1+i:])
    maxv = max(maxv,first+second)

#꿀벌벌
for i in range(1,T-1):
    first = sum(S[:-1])-S[i]
    second = sum(S[:i])
    maxv = max(maxv,first+second)

#벌꿀벌
for i in range(1,T-1):
    first = sum(S[1:i+1])
    second = sum(S[i:-1])
    maxv = max(maxv,first+second)
print(maxv)

추측으로는 반복문안에서 매번 sum을 구하기 때문에, 중복된 계산으로 시간초과가 나는 것 같다.

100점

from copy import deepcopy

N=int(input())
H=list(map(int, input().split()))
# 수열을 s에 그대로 카피한다
S = deepcopy(H)
result=0

for i in range(1, N):
    S[i] += S[i-1]

for i in range(1, N-1): # 오른쪽
    #마지막값 (전체 누적값)에서 벌 위치 두개를 빼주고, 
    #벌 한마리는 i이후부터 시작함으로 그 이전 값을 빼준것 
    result = max(result, 2*S[-1]-H[0]-H[i]-S[i])
    
for i in range(1, N-1): # 왼쪽
    #이번에는 두배를 하는게 아니라 따로 더해줘야 함
    #첫번째 벌: S[-1]-H[-1]-H[i]
    #두번째 벌: S[i-1]
    result = max(result, S[-1]-H[-1]-H[i]+S[i-1])
for i in range(1, N-1): # 중간
    #i는 꿀의 위치이다.
    #첫번째벌은 꿀까지의 누적합에서 자기 위치를 빼준다.
    #두번째벌은 전체 누적합에서 꿀까지의 누적합을 빼주고 자기 위치를 뺴준다.
    result = max(result, S[i]-H[0] + S[-1]-S[i-1]-H[-1])

print(result)

풀이방식

55점 풀이와는 다르게 누적합을 미리 구해두고 시작한다.

기본 접근방식은 같은데, 경우의 수를 다음과 같이 3가지로 나눈다.

벌 - 🐝
벌통 - 🪣
꿀은 안 그려지만 그려보면 🐝 🐝 🍯 🍯 🍯 🍯 🪣

3 가지 경우의 수

1. 🐝 🐝 🪣
2. 🪣 🐝-🐝
3. 🐝 🪣 🐝

---

1. 🐝 🐝 🪣

이 경우 🐝 한 마리는 첫번째 위치 고정, 🪣 은 마지막 위치 고정이다.

다른 🐝 한 마리만 반복문에서 i로 위치를 바꾸어주면서 최댓값을 max로 갱신한다.

💡 나머지 두 케이스도 마찬가지이지만, 벌은 벌통 방향으로만 이동하게 되고, 그렇게 되면 그 방향과 반대에 있는, 자신보다 이전 위치의 꿀은 따지 못한다.

ex. 벌이 index 2이고 벌통이 index 5에 있으면, 벌은 index 0과 1의 꿀을 따지 못하고 5가 있는곳까지 오른쪽으로만 일방통행한다.

그래서 벌통과 최대한 멀리 떨어져있는 곳에서 시작해서, 꿀을 최대한 많이 따는게 이득이다.

하지만 나머지 벌 한 마리의 위치가 변수인데, 왜냐면 이 벌의 위치에 따라서그 위치의 꿀은 따지 못하게 된다.

따라서 반복문으로 해당 벌의 위치를 변경해가면서 어떤 경우의 수로 최댓값이 나오는지 갱신해야 한다.

---

2. 🪣 🐝-🐝

이 경우 🐝 한 마리는 마지막 위치 고정, 🪣 은 첫번째 위치 고정이다.

나머지 🐝 한 마리만 반복문에서 i로 위치를 바꾸어주면서 최댓값을 max로 갱신한다.

---

3. 🐝 🪣 🐝

이 경우 🐝 한 마리는 첫번째 위치 고정, 두번째 🐝은 마지막 위치 고정이다.

🪣 만 반복문으로 위치를 바꾸어주면서 최댓값을 갱신한다. (이전 두 케이스와 달리 이번엔 벌이 아닌 꿀의 위치가 이동한다.)

각 케이스 (반복문)가 끝날때마다도 최댓값을 갱신해준다.

이렇게 되면 최댓값을 가질만한 모든 경우의 수를 다 살펴볼 수 있게 된다.