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

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

2018번: 수들의 합 5

문제

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

---

풀이

투 포인터 유형의 문제이다.  예제입력을 보자면

start와 end 포인터를 둔 다음에 3가지 case로 나누어서 상황에 맞춰 더해가면서 start와 end포인터를 옮긴다.

 

1) 자연수 N보다 작은 경우 - end포인터를 한칸 옮기면서 더해준다.

2) 자연수 N과 같은 경우 - 가지수를 1 올려주고 sum에서 현재 start포인터 값을 빼준 후에 한 칸 옮긴다.

이 상황에서

 

3) 자연수 N보다 큰 경우 -  sum에서 현재 start포인터 값을 빼준 후에 한 칸 옮긴다.

위 상황에서 sum 14이므로 1)를 적용하면 20이 되어버린다. 이 경우에는 sum보다 크기 때문에 start를 한 칸 옮겨준다.

위 상황을 계속보자면

자연수 N(15)보다 더 크니까 3)적용 

자연수 N과 같으니까 2) 적용

자연수 N보다 작으니까 1) 적용

이렇게 계속 end포인터가 숫자 N과 같아질때까지 계속 반복하면 된다.

---

#include <bits/stdc++.h>
using namespace std;

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

	int N; // 자연수
	int start_idx = 1;
	int end_idx = 1; 
	int sum = 1; 
	int ans = 1; // N경우 포함

	cin >> N;

	while(end_idx!=N) {
		if (sum == N) { // 정답일 경우 start 한 칸 
			ans++; 
			sum -= start_idx;
			start_idx++;

		}
		else if (sum < N) { // 자연수N보다 작을 경우
			end_idx++;
			sum += end_idx;

		}
		else { // 자연수N보다 클 경우 
			sum -= start_idx;
			start_idx++;
		}
	}

	cout << ans;

	return 0;
}