[BOJ 33921 // C++] 아름다운 수열

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 33921번 문제인 아름다운 수열이다.
문제는 아래 링크를 확인하자.

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

 

전형적인 0-1 Fractional Programming 문제이다. 0-1 Fractional Programming에 대한 설명은 다음 공부 일지에 서술하였다.

https://measurezero.tistory.com/2371

[PS/CP 공부기록] 05. 0-1 Fractional Programming, Dinkelbach's Algorithm

 

 

글쓴이는 구현 연습 겸 이 문제를 Dinkelbach's Algorithm으로 해결했다. 계산 과정에서 64비트 정수 자료형의 오버플로우가 발생할 수 있으므로, 구현 과정에서 128비트 정수 자료형을 사용했다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;
typedef __int128 lll;

ll N, K, X, Y = 1, XX, YY;
ll A[100001], B[100001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        cin >> B[i]; A[i] = B[i] * B[i];
        A[i] += A[i - 1], B[i] += B[i - 1];
    }
    XX = A[N], YY = B[N];

    while ((lll)X * YY != (lll)Y * XX) {
        X = XX, Y = YY;
        lll val = 0, mx = 0; int qL = 0, qR = 0;
        for (int i = 0, lft = 0; i <= N - K; i++) {
            val += (lll)(A[i] - A[i - 1]) * Y - (lll)(B[i] - B[i - 1]) * X;
            if (val < 0) val = 0, lft = i + 1;
            lll v = val + (lll)(A[i + K] - A[i]) * Y - (lll)(B[i + K] - B[i]) * X;
            if (v > mx) mx = v, qL = lft, qR = i + K;
        }
        if (mx) XX = A[qR] - A[qL - 1], YY = B[qR] - B[qL - 1];
    }

    cout << X / Y << '.'; X %= Y;
    for (int k = 0; k < 10; k++) {
        X *= 10;
        cout << X / Y;
        X %= Y;
    }
}