BOJ 21758번: 꿀 따기

문제

문제 바로가기> BOJ 21758번: 꿀 따기

21758번: 꿀 따기

 

풀이

벌 2마리와 벌통의 위치를 모두 다르게 설정해보는 방식으로 문제를 푼다면 시간 초과가 발생한다.

벌이 2마리, 벌통이 1개이므로, 총 3가지의 경우가 있다.

 

     1. 벌 벌 벌통

        이 경우, 첫 번째 벌은 가장 왼쪽에 있는 게 이득이다.

        따라서 반복문 O(N)을 통해 두 번째 벌의 위치를 지정해주고, 그 시점에서 얻을 수 있는 이익을 계산한다.

 

     2. 벌 벌통 벌

        이 경우, 첫 번째 벌은 가장 왼쪽에, 두 번째 벌은 가장 오른쪽에 있는 게 이득이다.

        따라서 반복문 O(N)을 통해 벌통의 위치를 지정해주고, 그 시점에서 얻을 수 있는 이익을 계산한다.

 

     3. 벌통 벌 벌 

        이 경우, 두 번째 벌은 가장 오른쪽에 있는 게 이득이다.

        따라서 반복문 O(N)을 통해 첫 번째 벌의 위치를 지정해주고, 그 시점에서 얻을 수 있는 이익을 계산한다.

 

#include<iostream>
#define MAX 100001
using namespace std;

int N;
int honey[MAX], sum[MAX];

void input(){
    cin >> N;

    int h;
    for(int i=1; i<=N; i++) {
        cin >> honey[i];
        sum[i] = sum[i-1] + honey[i]; // 누적 합
    }
}

void solution(){
    int ans = 0;
    for(int i=2; i<N; i++) {
        ans = max(ans, (sum[N]-honey[1]-honey[i])+(sum[N]-sum[i])); // 벌(1) 벌(i) 벌통(N)
        ans = max(ans, (sum[i]-honey[1])+(sum[N-1]-sum[i-1]));  // 벌(1) 벌통(i) 벌(N)
        ans = max(ans, sum[i-1]+(sum[N-1]-honey[i])); // 벌통(1) 벌(i) 벌(N)
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solution();
}