백준 2018 수들의 합 5 [C++] 풀이 및 코드 / 투포인터(two-pointer)

문제

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

입력

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

출력

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

코드

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	int sum = 1;
	int count = 1;
	int end = 1;
	int start = 1;
	while (end != n)
	{
		if (sum < n)
		{
			end++;
			sum += end;
		}
		else if (sum > n)
		{
			sum -= start;
			start++;
		}
		else if (sum == n)
		{
			count++;
			end++;
			sum += end;
		}
	}
	cout << count << endl;

	return 0;
}

풀이

자연수 N(1 ≤ N ≤ 10,000,000)이라는 정수의 연속된 자연수 합을 구하기 위해서는 많은 시간이 필요하게 된다

2초안에 nlogn 시간을 허비하기 보다, n의 시간을 요할 수 있는 알고리즘이 필요하다.

이 때 사용할 수 있는 알고리즘이 two pointer가 된다.

 

입력받은 정수가 15일 때를 먼저 생각 해 보자.

two pointer는 end와 start를 이용하게 되는데, 이의 원리는 간단하게 start부터~ end까지 더해가며 15를 찾는다고 생각하면 된다.

그러면 첫 end와 start는 시작 지점인 1로 초기화 된다.

마찬가지로 입력받은 정수와 같은지 비교하기 위한 변수인 sum도 1로 초기화 한다.

• 처음 iteration때 1을 더하거나 빼는 연산이 없다.

sum이 입력받은 정수(num)과 같을 때 정답++가 되는데, 이를 찾을 때 까지 sum을 더해주면 된다.

이는 조건에 따라 달라지게 되는데 이를 보면

num이 15고 sum은 1로 초기화 되어 있으니 현 상태는 sum < num이 된다.

따라서 sum < num일 때는, end 포인터를 오른쪽으로 옮겨(++) sum에 더해주면 된다.

 

 

 

이렇게 sum하고 end를 더해주며 end++을 하면 15와 같아지거나 15를 넘게 될 것이다.

첫번 째 15까지 여정은 다음과 같다.

 

초기 sum = 1

반복 1 : sum(1) > num(15)

end up

start : 1

end : 2

sum(3) : sum(1)+end(2)

 

반복 2 : sum(3) > num(15)

end up

start : 1

end : 3

sum(6) : sum(3)+end(3)

 

반복 3 : sum(6) > num(15)

end up

start : 1

end : 4

sum(10) : sum(6)+end(4)

 

반복 4 : sum(10) > num(15)

end up

start : 1

end : 5

sum(15) : sum(10)+end(5)

 

sum과 입력받은 정수(num)이 같을 때에는 정답(count)에 ++를 해주고 end를++ 한 후 더해준다.

 

그럼 다음과 같은 상태가 되는데, 이 때(sum > num)에는 start를 ++한 후 sum에서 start를 빼준다.

이는 즉 더해지는 값을 1에서 부터가 아닌 2에서부터로 시작하는 것과 같다.

따라서 점점 1+2+3+4+5에서 4+5+6 그리고 7+8을 찾을 수 있는 것이다.

이렇게 찾다 보면, end가 15가 되면서 반복이 끝나게 된다.

 

이 반복이 끝나는 조건을 end가 15가 되는 것으로 걸게 되는데 이때는 정답(count)값에 ++이 안되기에 count 초기화를 1로 해주면 된다.