[프로그래머스 C++] 숫자의 표현

문제 : 숫자의 표현

문제 설명

 Finn은 요즘 수학 공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현하는 방법이 여러 개라는 사실을 알게 되었습니다. 예를 들어 15는 다음과 같이 4가지로 표현할 수 있습니다.

• 1 + 2 + 3 + 4 + 5 = 15
• 4 + 5 + 6 = 15
• 7 + 8 = 15
• 15 = 15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

 

제한사항

• n은 10,000 이하의 자연수 입니다.

 

 분석

 규칙이 있나 생각하면 어려워지는 문제이다. 아무리 생각해도 명쾌한 규칙이 안 떠오른다. 하지만 제한 사항을 보면 10,000 이하의 자연수이다. 즉, 무식하게 푸는 방법이 정법인 문제이다.

 

 구현

using namespace std;

bool is_continuity(int n, int start)
{
	int sum = 0, idx = start;
	while (true)
	{
		sum += idx;
		idx++;
		if (sum == n) return true;
		else if (sum > n) return false;
	}
}

int solution(int n)
{
	int answer = 1;	// 자기자신을 무조건 가짐.
	int max_num = n / 2; // 더할 수 있는 최대수

	for (size_t i = 1; i <= max_num; i++)
	{
		if (is_continuity(n, i)) answer++;
	}

	return answer;
}

int main()
{
	cout << solution(15); // 4
	return 0;
}