41. 연속된 자연수의 합 (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆

HongongHB 2023. 7. 27. 18:43

#include <stdio.h>
#include <vector>

using namespace std;

int main()
{
	int n, p1, p2, cnt = 0;
	scanf("%d", &n);
	
	vector<int> num(n, 0);
	
	for(int i = 1; i < n; i++)
		num[i] = i;
	
	p2 = n-1;
	p1 = p2-1;
	while(p1 > 0 && p2 > 0)
	{
		int sum = 0;
		for(int i = p2; i >= p1; i--)
			sum += num[i];
			
		if(sum > n)
		{
			p1--;
			p2--;
		}
		else if(sum == n)
		{
			for(int i = p1; i <= p2; i++)
			{
				if(i == p2)
					printf("%d = ", i);
				else
					printf("%d + ", i);
			}
			printf("%d\n", n);
			cnt++;
			p1--;
		}
		else
			p1--;
	}
	
	printf("%d", cnt);
	return 0;
}

1. 위 방법은 투포인터 알고리즘 으로 푼 방식이다. 맨 뒤부터 시작해서 그 합이 n보다 크거나 같다면 두 포인터를 한 칸씩 왼쪽으로 옮기는 원리이다.

2. 이 방법으로 하면 시간복잡도 O(N)이 나온다.

#include <stdio.h>
#include <vector>

using namespace std;

int main()
{
	int n, temp, a = 1, cnt = 0;
	scanf("%d", &n);
	
	temp = n;
	n--;
	while(n > 0)
	{
		a++;
		n -= a;
		if(n % a == 0)
		{
			for(int i = 1; i < a; i++)
			{
				printf("%d + ", (n/a) + i);
			}
			printf("%d = %d\n", (n/a) + a, temp);
		}
	}
	printf("%d", cnt);
	return 0;
}

1. 매우 독특한 방식인데, 이 방법이 제일 좋은 방법인 거 같아 사용해보았다. (강의 코드)

2. 1부터 사용할 숫자의 합만큼 n에서 뺀 후 n을 사용할 숫자 갯수만큼 나누었을 때 나머지가 0이라면 n을 사용할 숫자 개수만큼 나눈 후 사용할 숫자를 더하는 방식이다.

말로 설명하면 어려우니 천천히 살펴보자.

- n을 사용할 숫자 개수만큼 나눈 후 사용할 숫자를 더하는 방식

12 / 2 = 6이다. 이 수를 사용할 숫자인 1과 2에 더하면 각각 7과 8이 된다. 7과 8을 더하면 15(temp, 최초의 n 값)이 된다.

사과 15개 중 2개의 바구니에 각각 1개, 2개씩 담았다. (사용할 숫자 1과 2, 15 - (1+2))

- 1부터 사용할 숫자(각 바구니에 담긴 사과 개수)의 합(전체 바구니에 담긴 사과 개수)만큼 n(전체 사과 개수)에서 뺀 후

만약 1과 2를 사용한다고 하면 1부터 사용할 숫자의 합 = 1 + 2 = 3 이 된다. 위 코드에서는 while문에 들어가기 전에 n--를 해주고, a++(1+1 = 2)를 해준 후 n - a 를 해주었기 때문에 15 - 2 - 1 = 15 - (1+2) = 12 와 같다.

- n을 사용할 숫자 개수(바구니 개수)만큼 나누었을 때 나머지가 0

사용할 숫자 개수는 1과 2로 총 2개이다. 이 개수로 n = 12 를 나누었을 때 나머지가 0일 때를 확인하는 것이다. 12 % 2 = 0 이기 때문에 나누어떨어진다. 이는 아래에서 살펴보겠지만 각 숫자에 공평하게 수를 나눌 수 있다는 뜻이다.

- n을 사용할 숫자 개수(바구니 개수)만큼 나눈 후 그 몫(공평하게 나눈 사과 개수)을 사용할 숫자(각 바구니에 담긴 사과 개수)에 더하는 방식

12 / 2 = 6이다. 이 수를 사용할 숫자인 1과 2에 더하면 각각 7과 8이 된다. 7과 8을 더하면 15(temp, 최초의 n 값)이 된다.