[swexpert] 7510. 상원이의 연속합 (c++, 누적합)

n이 최고 10^6이므로 n^2은 시간초과로 O(n)으로 풀어줘야 되는 문제이다.

 

n=15일 때

1, 2, 3, ... ,15 를 하나씩 더하면 누적합은 1, 3, 6, 10, ...  이렇게 될 것이다.

6인 경우 1~6까지 누적합이 21이되어 15를 넘게 되면 앞에서부터 하나씩 빼준다 (연속합을 구하니깐)

21에서 1을 빼변 20, 2를 빼면 18, 3을 빼면 15가 되어 4+5+6=15 인 또 하나의 경우를 구할 수 있다.

 

그러니 시작이 어디부터 인지 나타내는 변수 s를 만들고 누적합이 15를 넘을 때마다 시작점을 1씩 증가시키면 된다.

 

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;

int main(int argc, char** argv)
{
	int test_case;
	int T;
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case)
	{
		int n;
		cin >> n;
		int cnt = 0;
		int s = 1;
		int sum = 0;
		for (int i = 1; i <= n; i++)//10^6
		{
			sum += i;
			while (sum > n) {
				sum -= s;
				s++;
			}
			if (sum == n) {
				cnt += 1;
			}

		}
		cout <<"#"<<test_case<<" "<< cnt << endl;
		

	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}