(그리디) 백준 21758번 _ 꿀 따기 [Python]

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

21758번: 꿀 따기

 

그리디 알고리즘에서 "그리디" 즉 탐욕적이라는 말은 "현재 상황에서 지금 당장 좋은 것만 고르는 방법"을 의미한다.

 

이 문제를 풀면서 누적합과, A = max(A, B)를 통해 최댓값을 계속 업데이트 해주는 두 가지 개념에 대해 배울 수 있었다.

 

문제를 예시로 누적합에 대해 좀 더 자세히 말해보면, 우선 꿀 합에 대한 누적합은 다음과 같다.

# 코드 (문제에 주어진 예시)
n = 7
honey_place = [9,9,4,1,4,9,9]
prefix_sum=[]
prefix_sum.append(a[0])
for i in range(1,n):
  prefix_sum.append(prefix_sum[i-1]+honey_place[i])
print(prefix_sum)

# [9, 18, 22, 23, 27, 36, 45]

# prefix_sum
[9, 18, 22, 23, 27, 36, 45]

누적합을 구하는 이유는 벌들이 자신의 위치로 부터 꿀통의 위치까지 순차적으로 사이의 모든 꿀을 더해가기 때문이다.

 

누적합을 구했으면 그 다음은 꿀통의 위치부터 살펴 볼 필요가 있다.

꿀통의 위치는 크게 세가지로 나눌 수 있다.

1) 왼쪽 끝에 있을때

2) 오른쪽 끝에 있을때

3) 두 벌 사이에 있을때 (가운데)

 

1)과 2)의 경우 한쪽 끝에 꿀이 있으면 반대쪽 끝에는 반드시 벌 한마리가 위치해야한다. (직관적으로 생각했을때 벌이 최대한 꿀로부터 멀리 떨어져있어야 모으는 꿀의 양이 최대가 될 것이다.)

3)의 경우 꿀이 가운데에 있다면 벌들은 양 끝에 위치해야 할 것이다.

 

1) 꿀이 왼쪽 끝에 있을 때

(1) 꿀이 왼쪽 끝에 고정일때, (2) 벌1은 오른쪽 끝으로 고정이다

(1) 꿀이 왼쪽 끝에 있을 때

2) 꿀이 오른쪽 끝에 있을 때

(2) 꿀이 오른쪽 끝에 있을 때

3) 두 벌 사이에 꿀이 있을 때 (가운데)

(3) 두 벌 사이에 꿀이 있을 때 (가운데)

 

위 로직을 코드로 짜보면 

n = int(input())
ans = 0
honey_place = list(map(int,input().split()))
prefix_sum = []
prefix_sum.append(honey_place[0])
for i in range(1, n):
  prefix_sum.append(prefix_sum[i-1] + honey_place[i])
# 꿀통이 왼쪽 끝
for i in range(1, n-1):
  ans = max(ans,prefix_sum[n-2] + prefix_sum[i-1] - honey_place[i])
# 꿀통이 오른쪽 끝
for i in range(1, n-1):
  ans = max(ans, prefix_sum[n-1] - honey_place[0] + prefix_sum[n-1] - prefix_sum[i] - honey_place[i])
# 꿀통 가운데
for i in range(1, n-1):
  ans = max(ans,prefix_sum[n-2] - honey_place[0] + honey_place[i])
print(ans)

다음과 같다 !!

제출 결과는

100점 !!

당연히 통과 !!

 

* 참고로 처음 짠 코드는 함수도 세개나 만들고 너무나도 복잡하게 풀었는데 도저히 모르겠어서 포기했다 ..

아래 코드의 반례가 보이신다면 알려주세요 ,,

def honey_can_lst(honey_lst,h_idx,b1_idx,b2_idx):
    can_lst = []
    if h_idx < b1_idx:
        can_lst.extend(list(range(h_idx+1,b1_idx)))
    else:
        can_lst.extend(list(range(b1_idx+1,h_idx)))
    if b2_idx == None:
        return can_lst
    else:
        try:
            can_lst.remove(b2_idx)
            return can_lst
        except:
            pass
        return can_lst
    
def honey_sum(honey_lst,can_lst):
    honeysum = 0
    for i in can_lst:
        honeysum += honey_lst[i]
    return honeysum

def find_bee2(honey_lst,honey_place_idx,bee1_idx):
    num_lst = list(range(len(honey_lst)))
    num_lst.remove(honey_place_idx)
    num_lst.remove(bee1_idx)
    honey_sum = []
    for i in num_lst:
        honey_sum.append(((sum(honey_lst)-honey_lst[i]-honey_lst[bee1_idx]),i))
    return max(honey_sum)

N = int(input(""))
honey_lst = list(map(int,input("").split(" ")))
answer=[]
for n, honey in enumerate(honey_lst):
    honey_place = honey
    if n == 0:
        bee1 = (honey_lst[-2],len(honey_lst)-1)
        bee2 = (honey_lst[-1],len(honey_lst)-2)
    elif n == len(honey_lst)-1:
        bee1 = (honey_lst[0],0)
        bee2idx = find_bee2(honey_lst,n,0)[1]
        bee2 = (honey_lst[bee2idx],bee2idx)
    else:
        bee1 = (honey_lst[0],0)
        bee2 = (honey_lst[-1],len(honey_lst)-1)
    b1_can_lst = honey_can_lst(honey_lst,n,bee1[1],bee2[1])
    b2_can_lst = honey_can_lst(honey_lst,n,bee2[1],None)
    answer.append(honey_sum(honey_lst,b1_can_lst)+honey_sum(honey_lst,b2_can_lst)+honey_lst[n]*2)
print(max(answer))