백준] 2018 - 수들의 합 5

시간 제한 : 2초

메모리 제한 : 32MB

입력

첫 줄에 정수 N이 주어진다.

출력

입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오.

소스코드

#include <iostream>
using namespace std;
int main(void)
{
	int n, cnt = 0;
	cin >> n;
	for (int i = 1; i<=n;i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (n == (i * j + (j - 1)*j / 2))
			{
				cnt++;
				break;
			}
			else if (n < (i*j + (j + 1)*j / 2))
				break;
		}
	}
	cout << cnt;
}

Tip

수학적으로 한 번 생각해보자, 연속된 값들의 합이 N을 만들 수 있는지 판별하면 된다.

예를 들어 i부터 시작해서 i+j까지 가는 수열이 있다고 하자.

i+0, i+1, i+2, ... , i+j-1, i+j

그 합은 i*j + j*(j-1)/2가 될 것이다. 그럼 이것이 N이 되는지만 판별하면 된다. 그리고 계산의 효율성을 위해서 이보다 커진다고 하면 그 이후의 비교 작업은 무의미하므로 반복문을 중단시키면 된다.

수학적으로 생각해보면 이것보다 더 깔끔하게 끝낼 수 있는 작업이 있을 것 같다. 이 방법은 반복문과 기초적인 수열 개념에서 풀 수 있는 방법이다.