[백준/C++] 2018번: 수들의 합 5

문제

https://www.acmicpc.net/problem/2018

2018번: 수들의 합 5

---

문제 요약

자연수 n을 연속된 자연수들의 합으로 나타내는 가지수를 출력한다.

 

이 때, 사용하는 자연수는 n이하이다.

 

ex) 15를 나타내는 방법

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

---

코드

#include <iostream>

using namespace std;

int n;

int main() {
	cin >> n;

	int left = 0;
	int right = 0;
	int sum = 0;
	int cnt = 0;

	while (right <= n) {

		if (sum == n) {
			cnt++;
			right++;
			sum += right;
		}

		else if (sum < n) {
			right++;
			sum += right;
		}
		else {
			sum -= left;
			left++;
		}
	}

	cout << cnt;
}

---

코드 설명

투포인터 알고리즘을 이용한다.

 

0부터 n까지 1씩 증가하는 배열이 존재한다고 가정한다.

(실제로는 left와 right 내용 자체가 가리키는 배열의 위치이다. 즉, 배열이 필요없다.)

 

left, right 포인터 두 개를 자연수 0에 두고, 포인터 사이에 존재하는 자연수들의 합(sum)이

 

1. n보다 작으면, 오른쪽 포인터를 오른쪽으로 한 칸 옮기고

 

2. n보다 크면, 왼쪽 포인터를 오른쪽으로 한 칸 옮기고

 

3. n과 같으면, cnt를 1씩 증가시키고 오른쪽 포인터를 오른쪽으로 한 칸 옮긴다.

 

right 포인터가 n을 넘어가면 종료한다.

 

마지막으로 cnt의 개수를 출력한다.