백준 21758 꿀 따기(C++)

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

#include <iostream>
#include <vector>

using namespace std;

vector<int> honey;
vector<int> prefix;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    int ans = 0;
    cin >> n;

    honey.resize(n);
    prefix.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> honey[i];
        if (i == 0) {
            prefix[i] = honey[i];
        } else {
            prefix[i] = prefix[i - 1] + honey[i];
        }
    }

    //벌 꿀통 벌->꿀통의 위치를 조정해가며 계산
    for (int i = 1; i < n - 1; i++) {
        ans = max(ans, (prefix[i] - prefix[0]) + (prefix[n - 2] - prefix[i - 1]));
    }

    //벌 벌 꿀통->왼쪽 벌과 꿀통을 양쪽에 넣고 중간 벌의 위치를 조정해가며 계산
    for (int i = 1; i < n - 1; i++) {
        ans = max(ans, (prefix[n - 1] - honey[0] - honey[i]) + (prefix[n - 1] - prefix[i]));
    }


    //꿀통 벌 벌->중간 벌의 위치를 조정해가며 계산
    for (int i = 1; i < n - 1; i++) {
        ans = max(ans, (prefix[n - 2] - honey[i]) + prefix[i - 1]);
    }

    cout << ans;

    return 0;
}

1. 문제

n개의 장소와 각 장소에 있는 꿀의 양이 주어진다. 이 중 서로 다른 두 장소를 골라 벌을 배치하고, 벌과 다른 곳에 위치한 장소를 골라 벌통을 배치하려고 한다. 벌은 벌통 방향으로 가면서 꿀을 따는 데, 다음의 규칙을 따른다.

1. 두 마리가 모두 지나간 장소에서는 두 마리 모두 표시된 양 만큼의 꿀을 딴다. (벌통이 있는 장소에서도 같다.)
2. 벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다.

각 벌이 따는 꿀의 합을 최대로 하려고 할 때, 꿀의 양을 구하라.

2. 풀이

벌이 따는 꿀의 양은 기본적으로 벌이 위치한 장소의 다음 장소에서 벌통까지의 꿀의 양의 합이다. n이 10만까지이고, 경우의 수가 많으므로 누적 합을 사용하여 풀어야 한다.

    for (int i = 0; i < n; i++) {
        cin >> honey[i];
        if (i == 0) {
            prefix[i] = honey[i];
        } else {
            prefix[i] = prefix[i - 1] + honey[i];
        }
    }

꿀의 양을 입력받으면서 누적 합을 구해준다.

 

벌과 벌통의 위치는 세 가지 케이스로 나눌 수 있다.

 

 1. 벌 꿀통 벌

회색 장소가 벌의 위치, 검은색 장소가 벌통의 위치이다. 왼쪽에 배치한 벌은 9+4=13, 오른 쪽에 배치한 벌은 9+4+1+4=18, 총 31의 꿀을 모을 수 있다. 벌이 자신의 바깥쪽에 위치한 꿀을 채취하지 못하는 걸 막기 위해서는 이와 같이 벌을 양쪽 끝에 배치해야 최댓값을 기대할 수 있다.

    //벌 꿀통 벌->꿀통의 위치를 조정해가며 계산
    for (int i = 1; i < n - 1; i++) {
        ans = max(ans, (prefix[i] - prefix[0]) + (prefix[n - 2] - prefix[i - 1]));
    }

이 식과 같이 꿀통의 위치를 옮겨가면서 왼쪽 벌의 위치+1~벌통의 위치, 벌통의 위치~오른쪽 벌의 위치 -1까지의 꿀의 합을 각각 더해 준다.

2. 벌 벌 꿀통

1의 케이스와 같은 원리로 왼쪽 벌이 왼쪽 끝보다 안쪽에 있으면 바깥쪽의 꿀을 채취할 수 없고, 꿀통이 안쪽에 있으면 두 벌 모두 꿀통보다 오른 쪽에 있는 꿀을 채취할 수 없으므로 왼쪽 벌과 꿀통을 양쪽 끝에 배치하고, 가운데의 벌의 위치를 옮겨가면서 계산한다.

    //벌 벌 꿀통->왼쪽 벌과 꿀통을 양쪽에 넣고 중간 벌의 위치를 조정해가며 계산
    for (int i = 1; i < n - 1; i++) {
        ans = max(ans, (prefix[n - 1] - honey[0] - honey[i]) + (prefix[n - 1] - prefix[i]));
    }

 왼쪽 벌은 왼쪽 벌의 위치+1~벌통의 위치의 꿀의 합을 계산하는 데, 중간 벌의 위치에서는 2번 규칙에 의해 꿀을 딸 수 없으니 빼준다. 중간 벌은 중간 벌의 위치+1~벌통의 위치의 꿀의 합을 계산한다. 둘의 합을 더하면 꿀의 양을 계산할 수 있다.

 

3. 꿀통 벌 벌

    //꿀통 벌 벌->중간 벌의 위치를 조정해가며 계산
    for (int i = 1; i < n - 1; i++) {
        ans = max(ans, (prefix[n - 2] - honey[i]) + prefix[i - 1]);
    }

 2번과 같은 방법으로 계산해준다. 중간 벌은 맨 왼쪽(벌통의 위치)~벌의 위치-1까지 꿀을 더하고, 오른쪽 벌은 맨 왼쪽~벌의 위치-1(n-2)까지 더하는 데, 중간 벌이 위치한 장소의 꿀은 빼준다.

 

 세 케이스를 구해 max 함수로 최댓값을 구하여 ans에 저장했으니 이를 출력하면 정답을 구할 수 있다.