[C++] 백준 21758 : 꿀 따기

문제

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

 

 

풀이

 두 마리의 벌 중 하나는 항상 양 끝 위치 중 하나에 있어야 한다. 이렇게 생각하면 두 마리의 벌과 벌통의 위치에 대한 경우는 3가지로 분류할 수 있다.

1. 벌1 - 벌2 - 벌통 : 벌1이 시작 위치, 벌통이 마지막 위치에 존재하는 경우 -> 벌2의 위치를 변화시기키
2. 벌1 - 벌통 - 벌2 : 벌1이 시작 위치, 벌2가 마지막 위치에 존재하는 경우 -> 벌통의 위치를 변화시키기
3. 벌통 - 벌1 - 벌2 : 벌통이 시작 위치, 벌2가 마지막 위치에 존재하는 경우  -> 벌1의 위치를 변화시키기

 이제 각 경우에 대해 발생할 수 있는 최대의 꿀 획득량을 구하면 된다. 이때 주의해야 하는 것은 현재 장소가 최대 100000 개 존재할 수 있으므로, 만약 이중 for 문 등을 통해 각 경우에 대한 최대 획득량을 구하려고 하면 시간 초과가 발생한다.

 

 따라서 이 문제의 경우, 누적합을 미리 구해놓고 꿀 획득량을 구하는 데에 이용해야 한다.

 자세한 구현 내용은 코드의 주석을 참고하면 된다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

int n, total;
int honey[100000];
int prefix[100000];

int main()
{
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> honey[i];
    }
    
    // 누적합 구하기 
    prefix[0] = honey[0];
    for(int i=1; i<n; i++){
        prefix[i] = prefix[i-1] + honey[i]; 
    }
    total = prefix[n-1];
    
    int sum_honey = 0;
    
    // 벌1 - 벌통 - 벌2  : 벌통 기준, 벌1과 벌2 는 고정 
    for(int i= 1; i<n-1; i++){
        sum_honey = max(sum_honey, prefix[i] - honey[0] + total - prefix[i-1] - honey[n-1]);
    }
    
    // 벌1 - 벌2 - 벌통 : 벌1과 벌통 고정, 벌2 를 이동 
    for(int i=1; i<n-1; i++){
        sum_honey = max(sum_honey, total - honey[0] - honey[i] + total - prefix[i]);
    }
    
    // 벌통 - 벌2 - 벌1 : 벌통과 벌1 고정, 벌2 를 이동 
    for(int i = n-2; i>0; i--){
        sum_honey = max(sum_honey, total - honey[n-1] - honey[i] + prefix[i-1]);
    }
    cout << sum_honey << "\n";
    
    return 0;
}

 

 

 

메모

누적합을 이용하지 않았을 때, 그러니까 각 경우에 대해 꿀 획득량을 계산할 때마다 for 문을 이용했을 때에는 시간 초과가 발생하여 부분 정답 처리되었다. 누적합을 이런 경우에 발생할 수 있다는 점을 기억하기!