[백준] 21758 꿀 따기 (파이썬)

골드 Ⅴ

https://www.acmicpc.net/problem/21758

21758번: 꿀 따기

 

📄 문제

•  N개의 장소가 있다.
• 장소들 중 서로 다른 두 곳을 골라서 벌을 한 마리씩 둔다.
• 또, 다른 한 장소를 골라서 벌통을 둔다
• 두 마리 벌은 벌통으로 똑바로 날아가면서 지나가는 모든 칸에서 꿀을 딴다.
• 각 장소에 적힌 숫자는 벌이 지나가면서 꿀을 딸 수 있는 양이다.
• 두 마리가 모두 지나간 장소에서는 두 마리 모두 표시된 양만큼의 꿀을 딴다. (벌통이 있는 장소에서도 같다.)
• 벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다.

 

벌들이 딸 수 있는 가능한 최대의 꿀의 양을 계산하는 프로그램을 작성하라.

 

---

💡 아이디어

• 그리디 알고리즘이다.
• 벌, 벌, 꿀통 중 2개를 선택하여 양 끝을 고정하면 버리는 값이 줄어든다.
• 3가지 경우로 나누어 고정해볼수있다.
  • 벌 - 벌(이동) - 꿀통
  • 벌 - 꿀통(이동) - 벌
  • 꿀통 - 벌(이동) - 벌

• 양끝을 고정 시키지 않고 안쪽으로 이동가능하게 하면,
  • 왼쪽 끝은 이전의 꿀양을 버리게 되고
  • 오른쪽 끝은 이후의 꿀양을 버리게 된다.

• 시간초과가 일어날 수 있으므로 같은 값을 재 탐색하지 않기 위해 누적 합을 이용한다.
• 중간에 벌 또는 꿀통의 이동에 따른 값의 변화를 + - 로 변경해 주면서 비교한다.

 

1. 벌(고정)  벌(이동) 꿀통(고정)

• 왼쪽 끝: 벌
• 오른쪽 끝: 꿀통
• 중간에서 벌을 이동하며 최댓값을 찾는다.

 

왼쪽 끝 (고정)	중간 (이동)			오른쪽 끝 (고정)
벌 (A)	벌 (B)		...	꿀통
벌	m-1	벌 (B) m	...	꿀통
벌			...	꿀통

 

B의 위치를 순서대로 이동시키면,

• A는 B의 이전 위치 꿀을 가질 수 있고 B의 현재 위치는 가질 수 없다.
• B는 자신의 이전 위치의 꿀을 가질 수 없다.

 

따라서, 누적합에 B의 이전 위치(m-1)의 값을 한번 더하고 현재 위치(m)의 값을 두 번 뺀다.

 

왼쪽에 끝에 벌을 고정하지 않고 이동할 경우 이동한만큼 꿀의 양을 버리게 된다.

 

버려지는 양	벌	벌		...	꿀통
버려지는 양	버려지는 양	벌	벌	...	꿀통

 

2. 벌(고정)  꿀통(이동) 벌(고정)

• 왼쪽 끝: 벌
• 오른쪽 끝: 벌
• 중간에서 꿀통을 이동하며 최댓값을 찾는다.

 

왼쪽 끝 (고정)	중간 (이동)			오른쪽 끝 (고정)
벌 0	꿀통			벌 n-1
벌	m-1	꿀통 m		벌
벌			...	벌

 

이 경우에 가능한 값은 양 끝 값을 제외한 값들의 합에 꿀통의 현재 위치를 한번 더 더한 값이다.

 

벌 0	꿀통 (두번 더해지는 값)		...	벌 n-1
벌		꿀통 (두번 더해지는 값)	...	벌

 

따라서, 양 끝 값을 제외한 값들의 합 (꿀통이 이동 가능한 범위의 합) + 꿀통이 이동가능한 범위 중 최댓값을 하면 이 경우에서 가장 큰 값이 된다.

 

3. 꿀통(고정) 벌(이동) 벌(고정)

배열을 뒤집어 1번과 같이 풀이한다.

 

📝 문제 풀이 (Code)

최종 코드

n = int(input())
honey = list(map(int, input().split()))
reversedHoney = honey[::-1]

total = sum(honey[1:n-1])

# 첫 번째 경우

# 벌A 꿀통(이동) 벌B
# 꿀통 위치만 두번 더 해진다.
# 사이 값중 최대값만 비교
moveBarrel = total + max(honey[1:n-1])
# 벌A 벌B(이동) 꿀통
moveB = total * 2 - honey[1]*2 + honey[n-1]*2
# 꿀통 벌A(이동) 벌B (벌B 벌A(이동) 꿀통)
moveA = total * 2 - reversedHoney[1]*2 + reversedHoney[n-1]*2

ans = max(moveA, moveB, moveBarrel)

# 2번째 경우 부터
for m in range(2, n-1):
    # 벌A 벌B(이동) 꿀통
    moveB += honey[m-1] - honey[m]*2
    # 꿀통 벌A(이동) 벌B (벌B 벌A(이동) 꿀통)
    moveA += reversedHoney[m-1] - reversedHoney[m]*2

    ans = max(ans, moveB, moveA)

print(ans)

---

55점 코드

• 양 끝 고정을 고정하여 3가지 경우의 수로 구현
• sum 함수 이용

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
# 최댓값 저장
ans = 0
# 전체 꿀양
total = sum(arr)

for move in range(1,n-1):
    # 양 끝 고정
    # 벌A 벌B(이동) 꿀통
    beeA = total - arr[0] - arr[move]
    beeB = total - sum(arr[:move+1])
    ans = max(ans, beeA+beeB)

    # 벌A 꿀통(이동) 벌B
    ans = max(ans, total- arr[0]-arr[n-1]+arr[move])

    # 꿀통 벌A(이동) 벌B
    beeA = total - sum(arr[move:])
    beeB = total - arr[move] - arr[n-1]
    ans = max(ans, beeA + beeB)

print(ans)

 

11점 코드

• 조합을 이용

from itertools import combinations

n = int(input())
arr = list(map(int, input().split()))

ans = 0
# 완전 탐색
# 벌 위치 2개의 인덱스를 선택한다. 
idx = list(combinations(range(n),2))

# 꿀통 인덱스 k 에 따른 
for k in range(n):
    for a,b in idx:
        # 벌 a < 벌 b
        if k == a or k == b:
            continue
        if k < a:
            # 꿀통k 벌a 벌b
            ans = max(ans, sum(arr[k:a]) + sum(arr[k:b]) - arr[a])

        elif b < k:
            # 벌a 벌b 꿀통k
            ans = max(ans, sum(arr[a+1:k+1]) + sum(arr[b+1:k+1]) - arr[b])
        else:
            # 벌a 꿀통k 벌b
            ans = max(ans, sum(arr[a+1:k+1]) + sum(arr[k:b]))

print(ans)