[ boj : 10246 ] 부동산 경매

www.acmicpc.net/problem/10246

10246번: 부동산 경매

문제 : 연속된 정수들의 합으로 주어진 수를 만들 수 있는 경우의 수를 구해라!!!!

 

해설 : 이런 문제....즉, '입력의 제한'을 고려해야 하는 문제가 은근히 자주 나오는 것 같습니다. 저도 해맸습니다.

일단 먼저 우린 '연속된 정수'들의 합이라는 조건이 달려있다는 것을 알 수 있습니다. 

그럼 이것은 우리가 중학교??인가요???암튼 '시그마'라는 공식을 이용할 수 있겠죠.

 

시그마 (a~b) = 시그마(1~b) - 시그마(1~a) + b

 

그럼 먼저 이 공식을 이용하기 위해 prefix sum 을 이용한 배열 하나를 만들어 줍시다.

그 다음 이를 이용하려고 했더니 N의 제한이 100만인 것을 보고 갑자기 당혹스러워 집니다.

주어진 쿼리마다 모든 시그마 공식을 적용시켜 N을 만들 수 있는 경우의 수를 세려면 O(n^2)의 시간복잡도를 사용해야 하는데 최대 100만이니 이를 어쩐담....

 

그러나 곰곰이 생각해보면 '시그마(1~b) - 시그마(1~a) + b' 이 공식을 적용한 수들중 100만을 넘어가는 케이스는 n이 그리 크지 않을때도 넘어간다는 것을 알 수 있습니다.

당장 n이 1500만 되도 100만은 훌쩍 넘어가니까요. 그렇다면 '시그마(1~b) - 시그마(1~a) + b'이 100만을 넘어갈때 break로 루프문을 빠져나와도 충분한 시간 내에 '커팅'이 된다는 것을 의미하는 바 입니다.

 

시그마(1~50만) - 시그마(1~사백구십구만구천구백구) + 사백구십구만구천구 = 999999 이니 이 이후는 구할 필요도 없겠죠.

 

전 미리 prefix sum 배열을 구해놓은 뒤 '시그마(1~b) - 시그마(1~a) + b'이 100만 이하일 경우의 수를 싹다 미리 구해주었습니다. 그 후 입력된 쿼리마다 O(1) 시간에 답을 도출하게끔 해주었습니다.

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

ll prefix[1000001], cnt[1000001];

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

	prefix[1] = 2;
	for (int i = 2; i <= 500000; i++)
		prefix[i] = prefix[i - 1] + i + 1;

	for (int i = 1; i <= 500000; i++)
		for (int j = i - 1; j > 0; j--) {
			if (prefix[i] - prefix[j] + j + 1 > 1000000)break;
			cnt[prefix[i] - prefix[j] + j + 1]++;
		}
	int n;
	while (true) {
		cin >> n;
		if (n == 0)break;
		if (n == 1)cout << 0;
		else cout << cnt[n] + 1;
		cout << "\n";
	}
	return 0;
}