BOJ 13274. 수열

🙇‍♀️[Silver I] 수열 - 13274

문제 링크

성능 요약

메모리: 3592 KB, 시간: 52 ms

분류

정렬

제출 일자

2024년 6월 11일 15:35:34

문제 설명

지훈이는 수열을 좋아한다. 지금 지훈이는 size 가 N 인 수열을 가지고 놀고 있다. 지훈이는 K 개의 쿼리에 따라 수열을 변화시킬 것인데, 쿼리의 형식 및 작업 과정은 다음과 같다.

• L R X : 수열을 오름차순으로 정렬한 결과를 A[1], A[2], … , A[N]이라 하자. 우선 A[L], A[L+1], … , A[R]에 X 만큼 더한다. 그 결과 수열을 다시 오름차순으로 정렬한다.

쿼리들을 순서대로 모두 수행한 후의 수열을 출력하라.

입력

첫째 줄에 N 과 K 가 띄어쓰기로 구분되어 주어진다. (1 ≤ N ≤ 100000, 1 ≤ K ≤ 1000)

둘째 줄에 절댓값이 10¹⁸ 이하인, 수열을 이루는 N 개의 정수가 주어진다.

셋째 줄부터 K+2 번째 줄까지 쿼리 L R X 가 주어진다. (1 ≤ L ≤ R ≤ N, |X| ≤ 10⁹)

출력

쿼리들을 순서대로 모두 수행한 후의 수열을 출력한다.

🚀풀이

문제의 요건대로 작업을 하면 시간 초과가납니다.

그래서 새로운 방법으로 누적합을 계산해줘야합니다.

처음에 수열을 정렬합니다.
구간 변경 관리: 각 쿼리에 대해 구간에 더할 값을 기록합니다.
누적 합 적용: 마지막에 누적 합을 적용하여 최종 결과를 계산합니다.

아래 코드에서 위 구간 변경 관리를 하는 부분은 다음과 같습니다.

// 각 쿼리에 대해 처리
for (int i = 0; i < K; ++i) 
{
    int L, R;
    long long X;
    cin >> L >> R >> X;
    L--; R--; // 1부터 시작하는 인덱스를 0부터 시작하는 인덱스로 변환

    // delta 배열에 구간 변경 사항 기록
    delta[L] += X;
    if (R + 1 < N) 
    {
        delta[R + 1] -= X;
    }
}

delta[R + 1] -= X;을 해줌으로써 구간합이 끝났음을 알립니다.

실제 적용은 다음과 같이 합니다.

// 누적 합 계산 및 적용
long long cumulative = 0;
for (int i = 0; i < N; ++i) 
{
    cumulative += delta[i];
    arr[i] += cumulative;
}

변화량이 계속 기록되어 있으므로 문제의 요건에 성립하여 동작합니다.

그 후 최종적으로 정렬을 하면 원하는 출력값이 나옵니다.

🚀코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <climits>

using namespace std;

void solve()
{
    int N, K;
    cin >> N >> K;

    vector<long long> arr(N);
    for (int i = 0; i < N; ++i) 
    {
        cin >> arr[i];
    }

    // 수열 정렬
    sort(arr.begin(), arr.end());

    // 누적 변화량을 저장할 배열
    vector<long long> delta(N + 1, 0);

    // 각 쿼리에 대해 처리
    for (int i = 0; i < K; ++i) 
    {
        int L, R;
        long long X;
        cin >> L >> R >> X;
        L--; R--; // 1부터 시작하는 인덱스를 0부터 시작하는 인덱스로 변환

        // delta 배열에 구간 변경 사항 기록
        delta[L] += X;
        if (R + 1 < N) 
        {
            delta[R + 1] -= X;
        }
    }

    // 누적 합 계산 및 적용
    long long cumulative = 0;
    for (int i = 0; i < N; ++i) 
    {
        cumulative += delta[i];
        arr[i] += cumulative;
    }

    // 최종 수열을 다시 정렬
    sort(arr.begin(), arr.end());

    // 최종 결과 출력
    for (int i = 0; i < N; ++i) 
    {
        cout << arr[i] << " ";
    }
    cout << '\n';
}

int main()
{
	FILE* stream;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen_s(&stream, "input.txt", "rt", stdin);

	solve();

	return 0;
}