1024번: 수열의 합

Memo

• 수학적으로 푸는 방법이 떠오르지 않아서, 이분 탐색으로 풀었습니다.
• L부터 시작하여 100까지 증가시켜갑니다
• 이분탐색은 첫 번째 숫자 기준으로 돌립니다.
• 한 번이라도 이분탐색을 성공시키면, 그 자리에서 출력시킵니다.

Code

제출 날짜

2021/03/17

메모리

2016 KB

시간

0 ms

#include <iostream>
#define MAX_ 1000000000
typedef long long ll;
int N, L, ans;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::cin >> N >> L;
	ans = -1;
}

void binary_search(int b_min, int b_max, int length)
{
	ll val = 0;

	if (b_min > b_max)
		return ;
	int b_mid = (b_min + b_max) / 2;

	for (int i = 0 ; i < length ; i++)
		val += (b_mid + i);
	if (val == N)
	{
		ans = b_mid;
		for (int i = 0 ; i < length ; i++)
			std::cout << b_mid + i << " ";
		return ;
	}
	if (val < N)
		binary_search(b_mid + 1, b_max, length);
	else
		binary_search(b_min, b_mid - 1, length);
}

void solve()
{
	int i = L - 1;

	while (++i <= 100 && (ans == -1))
		binary_search(0, MAX_, i);
	if (ans == -1)
		std::cout << ans;
}

int main()
{
	input();
	solve();
	return (0);
}