[C++] 연속된 자연수의 합 🔥

📄문제

입력으로 양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방
법의 가짓수를 출력하는 프로그램을 작성하세요.
만약 N=15이면,
7+8=15
4+5+6=15
1+2+3+4+5=15 와 같이 총 3가지의 경우가 존재한다.

 

⬇️ 입력

첫 번째 줄에 양의 정수 N(7<=N<1000)이 주어진다.

15

 

⬆️ 출력

첫줄부터 각각의 경우의 수를 출력한다.
맨 마지막 줄에 총 개수를 출력한다.

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

 

📝 풀이

#include <iostream>
#include <stack>

using namespace std;
int main()
{
	int N;
	stack<pair<int, int>> pairs;

	scanf_s("%d", &N);

	for (int i = 1; i <= N; ++i)
	{
		int sum = 0;

		for (int j = i; j < N; ++j)
		{
			sum += j;

			if (sum == N)
			{
				pairs.push(pair<int, int>(i, j));
				break;
			}
			else if (sum > N)
				break;
		}
	}

	int cnt = pairs.size();
	while (!pairs.empty())
	{
		pair<int, int> pair = pairs.top();
		pairs.pop();

		int sum = 0;

		for (int i = pair.first; i < pair.second; ++i)
		{
			printf("%d + ", i);
			sum += i;
		}
		printf("%d = %d\n", pair.second, sum + pair.second);
	}

	printf("%d", cnt);
}

• 1부터 증가시켜 덧셈을 하여 N과 같아지는지 확인하는 단순한 코드입니다.
• 하지만 이 해결 방법은 시간 복잡도가 O(n^2)이므로 더 효율적인 방법을 학습하였습니다.

 

#include <iostream>

using namespace std;
int main()
{
	int N, totalCnt = 0;
	scanf_s("%d", &N);

	// i는 2, 두자리의 연속 부터 시작
	// i는 i자리의 개수로 가능한가? 를 검사
	// 예를들어 i가 2면, 두자리의 합으로 가능한지 검사
	for (int i = 2; ; ++i)
	{
		// N에서 뺀 나머지 수
		// i가 2라면, N - 1 - 2를 통해 12가 나머지
		int remain = N - (i * (i + 1) / 2);  

		if (remain < 0)
			break;

		// remain이 i로 나누어지는지?
		// 나누어진다면, i자리의 수로 표현이 가능해짐
		if (remain % i != 0)
			continue;

		int sum = 0;
		int quotient = remain / i; // remain을 i로 나눈 몫
		++totalCnt;

		// quotient과 j를 더한 값들로 표현
		// 예를들어 i가 2인 상태에서 remain이 6이라면
		// 7 + 8 = 15로 표현 가능
		for (int j = 1; j < i; ++j)
		{
			printf("%d + ", quotient + j);
			sum += (quotient + j);
		}

		printf("%d = %d\n", quotient + i, sum + quotient + i);
	}

	printf("%d", totalCnt);
}

위 코드를 이해하기 위해서 아래의 설명을 읽어보세요.

30개의 사과를 n개의 바구니에 연속된 개수로 둬야합니다. 만약 n이 2라고 가정해봅시다.
두개의 바구니에 사과를 일단 1개, 2개씩 두었습니다. 남은 사과의 개수는 27개입니다.
두개의 바구니를 연속된 개수로 채우기 위해서는 남은 사과의 개수 27개를 반으로 나눠야하지만, 27 % 2 = 1로 나누어 떨어지지 않습니다. 그러므로 30은 두개의 연속된 수로 더할 수 없습니다.

이번에는 30개의 사과를 3개의 바구니에 연속된 개수로 둬 봅시다.
세개의 바구니에 각각 사과를 1, 2, 3개씩 두었습니다. 그러면 남은 사과의 개수는 24개(30 - 1 - 2 - 3)입니다.
24개의 사과를 3개의 바구니에 나누어 담아야 하기 때문에 24를 3으로 나누어봅시다. 24 % 3 = 0 이므로 정확히 나누어 떨어져 몫은 24 / 3 = 8 입니다.
몫이 나왔기 때문에 각 바구니에 8개씩을 채웁니다.
결과로 바구니에 각각 9, 10, 11개의 사과가 담겨져 있습니다. 이를 표현하면 9 + 10 + 11 = 30이 됩니다.

나머지 방법도 n = 4, 5, 6 ... 으로 검사하면 답을 찾을 수 있습니다.