BOJ 19847 여우 신탁

문제 링크입니다.

변하지 않는 것

여우 신이 X개의 수 중 하나를 선택했다고 합시다. 우리는 마지막 신탁까지 내린 뒤 0부터 X-1 까지의 수가 각각 어느 수로 바뀌는 지를 알아내면 됩니다. 또는, 마지막 신탁까지 내린 뒤 각 수가 몇 번 나타나는 지를 확인할 수만 있어도 좋습니다.

실제로 신탁을 내리다 보면 여러 개의 수들이 하나의 수로 겹쳐질 것이고, 그 뒤로는 무슨 짓을 해도 다시 분리될 수가 없으니 도착하는 수의 빈도를 관리하는 쪽이 매번 X개의 수를 모두 생각하는 것보다 유리할 것입니다.

3개의 수 중 하나를 필요로 하는 여우에게 신탁을 내려주면, 여우 신이 지금 들고 있는 수는 0 이상 2 이하가 됩니다. 그 뒤에 5개의 수 중 하나를 필요로 하는 여우가 오면, 여우 신이 들고 있는 수를 5로 나눈 나머지를 취해도 그 수가 그대로 나가게 됩니다.

일반적으로 어떤 신탁을 내려준 뒤에 그보다 큰 수가 요청으로 들어오면, 그냥 전에 줬던 수를 그대로 주는 것으로 충분합니다. 요청이 들어올 때마다 지금 여우가 들고 있을 수 있는 가장 큰 수부터 거꾸로 보면서 나눌 수 있으면 나눠주는 방식으로 가면, X-1부터 0까지의 각 수를 많아봤자 한 번 나누게 됩니다. 투 포인터스럽게 구현할 수 있습니다.

나누는 것조차 귀찮아서 그냥 신탁으로 내려줘야 하는 수의 범위에 안 들어가면 그 범위만큼 뺀 값에 밀어넣는 방식으로 구현했습니다. 나눗셈은 어차피 뺄셈의 반복이고, 궁극적으로는 범위 밖의 수는 전부 나눠지는 거라 결과는 같습니다.

총 시간 복잡도 $\mathcal{O}(N+X)$에 문제를 해결할 수 있습니다.

코드

부동 소수점 오차에 유의하세요. 빈도를 관리하는 동안에는 정수 자료형을 쓰되, 출력 시에만 double 자료형을 쓰는 정도로 충분합니다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int d[1234567];

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n, now; cin >> n >> now; ll tot = now; for(int i = 0; i < now; i++) d[i] = 1;
	for(int i = 1; i < n; i++){
		int x; cin >> x;
		for(;now > x; now--){
			d[now-1-x] += d[now-1];
		}
	}
	ll ans = 0;
	for(int i = 0; i < now; i++) ans += i*d[i];
	cout << setprecision(12) << fixed << double(ans) / tot;
}