[C++][백준 13274] 수열

문제

접근 방법

문제 자체는 간단해 보이지만 문제가 주는 데이터는 간단하지 않다.
정수의 합이 int의 범위를 벗어나고 매 순간 정렬을 요구하는데 정렬에 사용될 값의 개수가 최대 100000이기 때문이다.

1000번 동안 100000개의 정렬을 한다면 시간 초과를 할 수 있다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int N, K, L, R, X;
vector<ll> A;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> N >> K;

    A = vector<ll>(N);

    for (ll &a : A)
    {
        cin >> a;
    }

    sort(A.begin(), A.end());

    while (K--)
    {
        cin >> L >> R >> X;

        --L;

        for (int i = L; i < R; ++i)
        {
            A[i] += X;
        }

        if (X < 0)
        {
            sort(A.begin(), A.begin() + R);
        }
        else
        {
            sort(A.begin() + L, A.end());
        }
    }

    for (const ll &a : A)
    {
        cout << a << " ";
    }
    return 0;
}

풀이

양수를 더할 때는 변화될 수 있는 값의 범위는 L에서부터 N까지이다.
음수를 더할 때는 0부터 R까지이다. 이유는 수를 더하면 부호에 따라 해당 방향으로 위치가 이동하기 때문이다. (0에서 양의 무한대를 더하면 N번째에 도달할 것이다, N에서 음의 무한대를 더하면 0번째에 도달할 것이다)

그렇기에 양수일 때는 L부터 N까지, 음수일 때는 0부터 R까지 정렬을 하게 하여서 부분적으로 정렬을 하게 해준다.

그래도 의문이 생길 것이다. L과 R의 범위는 1부터 N까지 가능하기에 매 순간 100000일 것이고 결국엔 stl의 sort로는 시간 초과가 나올 것 같기 때문이다. 그래서 찾아보니 stl의 sort는 introsort를 사용해서 상황에 따라 정렬 알고리즘을 전환한다고 한다. 그렇기에 최악의 상황을 면하는 거 같다.

int의 범위를 벗어나는 건 long long으로 대체하면 된다.

한 가지 실수를 했었는데 계산은 long long으로 해놓고 출력은 int로 해서 왜 틀렸는지 고민하고 있었다.