[백준 2737] 연속 합

문제 링크 => 2737번: 연속 합 (acmicpc.net)

2737번: 연속 합

---

알고리즘이 수학으로 분류되었지만 binary search 를 이용하여 해결했다.

 

문제는 굉장히 간단하다.

 

숫자 N 에 대하여 2개 이상의 연속하는 수의 합이 나올 수 있는 모든 경우의 수를 구하는 문제이다.

 

간단하게 생각해본다.

 

임의의 수 (x > 0) 에 대하여 다음과 같은 작업을 계속 해준다.

 

(1) 연속하는 수 2개 )

     x + (x + 1) = N  를 만족하는 x 가 있으면 경우의 수를 counting 한다.

 

(2) 연속하는 수 3개 )

     x + (x + 1) + (x + 2) = N 를 만족하는 x 가 있으면 경우의 수를 counting 한다.

 

(3) ...

 

(4) 연속하는 수 i개 )

     x + (x + 1) + (x + 2) + ... + (x + (i - 1)) = N 를 만족하는 x 가 있으면 경우의 수를 counting 한다.

 

이렇게 해서 연속하는 수가 2개 부터해서 i 개 까지 linear 하게 접근하여 binary search 를 이용하여

 

x를 구할 때 N 값과 동일한 경우 counting 하고 마지막으로 결과를 출력해주면 끝이다. 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <queue>
#include <stack>
#define endl '\n'
#define INF 1000000000
#define ll long long

using namespace std;

ll pow_31;

void test() {

	int N, cnt = 0;
	ll a = 2, b = 1;
	cin >> N;
	for (int i = 0; i < 100000; i++) {
		ll low = 0, high = pow_31;
		while (low <= high) {
			ll mid = (low + high) / 2;
			if (a * mid + b == N) break;
			else if (a * mid + b < N) low = mid + 1;
			else high = mid - 1;
		}
		ll mid = (low + high) / 2;
		if (mid > 0 && a * mid + b == N) {
			cnt++;
		}
		b += a, a += 1;
	}

	cout << cnt << endl;
}

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

	pow_31 = 1;
	for (int i = 1; i <= 31; i++) pow_31 *= 2;

	int n;
	cin >> n;
	while (n--) {
		test();
	}

	return 0;
}