정올 5662번: 도넛 한 입 (Donut)

문제 설명

도넛을 한 입 먹어서 먹을 수 있는 최대 맛을 구하는 문제다.

도넛은 N등분으로 나눠지며 각 조각의 맛이 -100 이상 100 이하 정수로 주어진다.

이 때, 한 입은 연속한 구간을 의미하며 한 입에 도넛을 통채로 먹는 것도 가능하지만, 최소 한 조각은 무조건 먹어야한다.

 

생각

문제를 딱 읽고 든 생각은 연속합 구간 중 최대를 구하는 문제구나 (그렇게 써져있음)

투포인터로 구현하면 되겠다. 라고 생각하고 코드를 짰는데 틀렸습니다.

이때까지 구했던 일반적인 누적합 문제는 배열에서 돌아가는 누적합이었다. 

그런데 이 문제는 배열의 처음과 끝이 연결될 수 있고, 원형으로 봐야한다.

 

따라서 일반적인 부분합 구하기(투포인터로 left, right 잡아서)를 이용하고 구간이 (N-1)~0 에 걸쳐져 있다면 따로 0~(left-1) 구간에 대해 계산해주었다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    vector<int> arr(N);
    vector<int> sum(N);
    for (auto &i : arr) cin >> i;
    sum[0] = arr[0];
    for (int i=1 ; i<N ; i++) sum[i] = sum[i-1] + arr[i];

    int left = 0, right = 0;
    int total = 0;
    int result = -101;

    while (right < N) {
        total += arr[right++];
        result = max(result, total);
        while (total < 0 && left < right) {
            total -= arr[left++];
            if (left != right) result = max(result, total);
        }
    }

    int maxSum = 0;
    for (int i=0 ; i<left-1 ; i++) {
        maxSum = max(maxSum, sum[i]);
    }
    if (left != right) result = max(result, total + maxSum);

    while (left < right) {
        total -= arr[left];
        if (left + 1 != right) result = max(result, total + maxSum);
        maxSum = max(maxSum, sum[left]);
        ++left;
    }

    cout << result;
}

 

 

피드백

풀이 이후 Claude Opus 5로 피드백을 요청했다.

기존 코드를 카데인으로 짜면 더 수월하게 짤 수 있을 뿐 아니라

구간이 (N-1)~1에 걸쳐져 있는 경우를 전체 합에서 최소 부분합을 빼는 것으로 생각하면

매우매우 우아하게 짤 수 있다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    vector<int> arr(N);
    for (auto &i : arr) cin >> i;

    int best = -101;
    int worst = 101;

    int cur = 0, cur2 = 0;
    int sum = 0;

    for (auto x : arr) {
        sum += x;
        cur = max(x, cur + x);
        cur2 = min(x, cur2 + x);

        best = max(best, cur);
        worst = min(worst, cur2);
    }

    cout << (best < 0 ? best : max(best, sum - worst));
}

두 구간으로 쪼개지는 경우를 여사건의 개념으로 생각하는 방식은 생각도 못했다..