취미로 코딩하기

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

이번에 볼 문제는 백준 15825번 문제인 System Call이다.
문제는 아래 링크를 확인하자.

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

문제의 답이 될 수 있는 버퍼의 크기는 1 이상 50만 이하의 값으로 매우 제한적임을 관찰하자. 따라서 1 이상 50만 이하의 정수 X에 대하여 버퍼의 크기가 X일 때 read를 호출해야 하는 횟수를 알고 있다면 각 버퍼 크기의 경우마다 드는 시간을 직접 조사해보는 것으로 문제를 해결할 수 있게 될 것이다. 이 횟수들을 빠르게 구하는 방법을 설계해보자.

먼저, 크기가 F인 파일 하나에 대하여 버퍼의 크기가 i-1일 때와 i일 때의 필요한 read 호출횟수가 변하는 i값이 무엇인지를 생각해보자. 조금 생각을 해보면 이러한 i값은 오직 O(sqrt(f))개만이 존재함을 알 수 있고, 이를 구해내는 것 또한 O(sqrt(F))의 시간복잡도로 해낼 수 있음을 알 수 있다.

위와 같은 i값들을 모두 구한다면 파일 크기 F에 대하여 i>1인 정수 i에 대해 "버퍼의 크기가 i-1에서 i로 바뀌었을 때 감소하는 read 호출 횟수"를 계산할 수 있게 된다. 각 파일에 대한 이와 같은 자료를 모으면 파일 N개에 대하여 "버퍼의 크기가 i-1에서 i로 바뀌었을 때 감소하는 read 호출 횟수"의 배열(크기 50만)을 만들 수 있게 된다.

위 작업의 시간복잡도는 O(Nsqrt(F)) (N: 파일의 개수, F: 파일의 크기)로, 이는 문제를 해결하기에 충분한 시간복잡도이다.

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

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

ll N, T;
ll cnt[500001], C;
ll ans; int ansi = 1;

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

	cin >> N;
	while (N--) {
		int F; cin >> F;
		vector<pair<int, int>> vec1, vec2;
		int idx = 1;
		while (idx * idx < F) {
			int y = (F - 1) / idx + 1;
			vec1.emplace_back(make_pair(idx, y));
			vec2.emplace_back(make_pair(y, idx));

			idx++;
		}
		if (idx * idx == F) vec1.emplace_back(make_pair(idx, idx));
		while (!vec2.empty()) {
			vec1.emplace_back(vec2.back());
			vec2.pop_back();
		}

		int vsize = vec1.size();
		
		C += vec1[0].second;
		for (int i = 1; i < vsize; i++) {
			cnt[vec1[i].first] += vec1[i - 1].second - vec1[i].second;
		}
	}

	cin >> T;
	ans = (T + 1) * C;
	for (ll i = 2; i < 500001; i++) {
		C -= cnt[i];
		ll tmp = (T + i) * C;
		if (tmp < ans) ans = tmp, ansi = i;
	}

	cout << ans << ' ' << ansi;
}