취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24838번 문제인 배열 구간합 놀이이다.
문제는 아래 링크를 확인하자.

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

크기 배열의 각 칸 x에 대하여 cnt[x]를 M개의 구간 중 몇 개의 구간이 x를 포함하는지를 나타내는 배열이라 하자. 모든 x에 대한 cnt[x]를 알 수 있다면 cnt[x]와 A의 각 원소들을 크기순으로 짝을 맞춰 곱해 더하는 greedy 전략으로 문제를 해결할 수 있음을 관찰할 수 있다.

cnt[x]의 경우 1차원에서의 imos법을 이용해 O(N + M)의 시간복잡도로 구할 수 있다. 구체적으로, 먼저 각 구간 [L,R]에 대하여 cnt[L]에 1을 더하고 cnt[R+1]에 -1을 더하는 것을 반복하자. 이러한 작업뒤에 현 cnt배열을 cnt배열의 구간합 배열로 바꾸면 구하려는 cnt배열을 얻을 수 있다.

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

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;

int T;
int N, M;
int arr[50001];
int cnt[50001];
ll fact[50001];

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

	fact[0] = fact[1] = 1;
	for (ll i = 2; i < 50001; i++) fact[i] = (fact[i - 1] * i) % 1000000007;

	cin >> T;
	while (T--) {
		memset(arr, 0, sizeof(arr));
		memset(cnt, 0, sizeof(cnt));

		cin >> N >> M;
		for (int n = 0; n < N; n++) cin >> arr[n];
		while (M--) {
			int L, R; cin >> L >> R;
			cnt[L - 1]++, cnt[R]--;
		}
		for (int n = 1; n < N; n++) cnt[n] += cnt[n - 1];

		sort(arr, arr + N);
		sort(cnt, cnt + N);

		ll ans = 0;

		for (int i = 0; i < N; i++) {
			ans += (ll)arr[i] * (ll)cnt[i];
		}

		ll ans2 = 1;
		int old = cnt[0]; ll combo = 1;
		for (int i = 1; i < N; i++) {
			if (cnt[i] == old) combo++;
			else {
				ans2 = (ans2 * fact[combo]) % 1000000007;
				old = cnt[i], combo = 1;
			}
		}
		ans2 = (ans2 * fact[combo]) % 1000000007;

		cout << ans << ' ' << ans2 << '\n';
	}
}