백준 2018 수들의 합 C/C++

수들의 합 5 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

32 MB

7492

3386

2627

48.902%

문제

어떠한 자연수 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을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

예제 입력 1 복사

15

예제 출력 1 복사

4

 

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n,pos1=1,pos2=1,sum=1,cnt=1;
	cin >> n;

	while (pos2 != n)
	{
		if (sum == n)
		{
			cnt++, pos2++;
			sum += pos2;
		}
		else if (sum > n)
		{
			sum -= pos1;
			pos1++;

		}
		else
		{
			
			pos2++;
			sum += pos2;
		}
	}

	printf("%d", cnt);
	return 0;
}

 

투포인터 문제다.

투포인터 문제라는 건, 2개의 포인터를 사용하여 문제를 푸는 것이다.

이렇게만 말하면 무슨 소리인지 모르니, 그림으로 봐보자.

 

 

1~15까지의 연속된 숫자가 있다면, 이를 가리키는 포인터(pos1, pos2)가 있다, 이 가리키는 포인터들이 움직이면서 값을 계산하는 것이다.

그렇다면 자연수의 합은 어떻게 계산할 수 있을까?

 

우선 pos1은 시작지점을 뜻하며, pos2는 끝지점을 뜻한다.

pos1= 1, pos2=1이면, 1에서 시작해 1로 끝나는 것이므로 1을 의미한다.

pos1=1, pos2=4면, 1+2+3+4=10 을 의미한다.

pos2=2, pos2=4면, 2+3+4=9를 의미한다.

 

이를 위해 포인터의 이동 원칙을 설정한다.

sum>n: sum= sum - pos1, pos1++

sum<n: pos2++; sum+=pos2;

sum==n: pos2++; sum=sum+pos2; cnt++;

 

 

만약 n이 15인데, sum이 18이다. 그럼 앞에서부터 값을 하나씩 뺀다.

n이 15고, sum이 18이라고 하자.

sum에서 pos1이 가리키던 1을 배고, pos1을 2로 옮긴다.

그러면 sum은 17이 된다.

pos1이 2니까 다시 sum에서 -2를 뺀다. 그리고 pos1은 3이 된다.

이 때 sum = 15 = n으로 같게 되고 자연수의 값을 찾았으므로 cnt를 +1한다.

이 때는 pos2를 늘린다.

그러면 이제 새로운 범위의 값이 나오고 이 값을 조정해나가면서 원하는 값이 나올 때 cnt를 출력한다.