[KOI 2021 1차대회 중등부] 21758번-꿀 따기

중요 지식

---

그리디 - 모든 경우의 수를 조사해서 최적의 값을 찾는다

코드

---

#include <iostream>

using namespace std;

int N;
int bees[100001];

int main(){
    int total = 0, dup, ans = 0;
    cin >> N;

    for(int i = 0; i < N; ++i){
        cin >> bees[i];
        total += bees[i];
    }

    // 벌 - 통 - 벌
    for(int i = 1; i < N - 1; ++i){
        dup = bees[i];
        ans = max(ans, total - bees[0] - bees[N - 1] + dup);
        
    }
    
    // 벌 - 벌 - 통
    dup = bees[N - 1];
    for(int i = N - 2; i > 0; --i){
        ans = max(ans, total - bees[0] - bees[i] + dup);
        dup += bees[i];
    }

    // 통 - 벌 - 벌
    dup = bees[0];
    for(int i = 1; i < N - 1; ++i){
        ans = max(ans, total - bees[N - 1] - bees[i] + dup);
        dup += bees[i]; 
    }
  
    cout << ans;

    return 0;
}

풀이

---

먼저 알아둬야할 변수

1. total : 모든 꿀의 합

2. bees[] : 꿀이 있는 자리

3. dup : 두 벌의 겹치는 꿀의 합

 

함수 하나하나 살펴보기

1. 벌통벌

양쪽 벌이 놓여진 자리를 뺀 모든 꿀의 합에 통이 놓여진 자리의 꿀을 한번 더 더하면서 나온 값중 최적의 값을 탐색.

for(int i = 1; i < N - 1; ++i){
    dup = bees[i];
    ans = max(ans, total - bees[0] - bees[N - 1] + dup);
}

2. 벌벌통

왼쪽 벌이 놓여진 자리를 뺀 모든 꿀의 합에 오른쪽 통에서부터 꿀을 더하면서, 벌이 놓여진 자리의 꿀을 뺀 값중 최적의 값을 탐색.

dup = bees[N - 1];
for(int i = N - 2; i > 0; --i){
    ans = max(ans, total - bees[0] - bees[i] + dup);
    dup += bees[i];
}

3. 통벌벌

오른쪽 벌이 놓여진 자리를 뺀 모든 꿀의 합에 왼쪽 통에서부터 꿀을 더하면서, 벌이 놓여진 자리의 꿀을 뺀 값중 최적의 값을 탐색.

dup = bees[0];
for(int i = 1; i < N - 1; ++i){
    ans = max(ans, total - bees[N - 1] - bees[i] + dup);
    dup += bees[i]; 
}

 

벌벌통과 통벌벌 더 이해하기 ( 예시: 통벌벌 )

1. dup의 초기값

dup = bees[0];

dup는 사용할 때 일일히 초기화시켜야하는데 겸사겸사 통의 꿀을 넣으면 for문을 1회 줄일 수 있다

 

2. 최적의 값을 구하는 구문

max(ans, total - bees[N - 1] - bees[i] + dup)

total - bess[N - 1] - bees[i] : 두 벌의 자리의 꿀을 뺀 모든 꿀의 합

dup :  통에서부터 현재 벌의 자리까지의 겹치는 꿀의 합 

 

3. 겹치는 꿀을 구하는 구문 

dup += bees[i]; 

왼쪽 벌의 자리의 꿀을 더하는 구문이 마지막에 실행되는 이유는 벌이 있는 자리의 꿀은 자신을 포함한 어느 벌도 구하지 못하므로 왼쪽 벌의 자리를 결정할 때 그 자리의 꿀만큼 오른쪽 벌의 꿀을 제거해야 한다

여기서 왼쪽 벌의 자리의 꿀을 먼저 넣는다면 왼쪽 벌과 오른쪽 벌의 꿀을 각각 제거해야 하므로 수식이 약간 복잡해진다