백준 BOJ 2018 - 수들의 합 5

오늘의 USACO(6)

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

2018번: 수들의 합 5

[s,e] 구간의 합이 N이 되도록 하는 s,e 쌍의 갯수를 구하는 문제.

처음에 문제를 보고 들었던 생각은 누적합 배열 이었고,

그래서 구간을 편의상 (s,e] 로 조정한 다음,

 

N의 범위 천만까지의 연속된 자연수의 합을 담아두는 prefix 배열을 만들어서

prefix[e] - prefix[s] 로 (s,e] 구간의 자연수의 합을 구하려는 생각을 했었다.

 

일단 이렇게 자연수의 합을 O(1) 시간에 구할 수 있게 된 다음에는,

s <= e임이 항상 보장되기 때문에 투 포인터 알고리즘을 적용할 생각을 했다.

 

만약 prefix[e] - prefix[s] 가 N보다 작거나 같다면, 더 많은 숫자를 더해줘야 하기 때문에, e를 증가시켰고,

prefix[e] - prefix[s]가 N보다 크다면, 더하는 숫자를 줄여야 하기 때문에 구간을 줄이고자 s를 증가시켰다.

 

하지만 이 풀이로는 메모리 제한에 걸리기 때문에 AC를 받을 수 없었고,

 

(s,e] 구간의 합을 다른 방법을 통해 O(1) 에 구하려는 생각을 해야했다.

풀이

(s,e] 구간이 1씩 증가하는 등차수열이기 때문에,

구간에 대해서 등차수열의 합 공식을 적용해줄 수 있고,

이 공식을 통해서 O(1) 시간에 자연수의 합을 구할 수 있다.

 

소스코드 펼쳐보기

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

//ll prefix[10000001] = {0};

int main(){
	//for(int i=1; i<=10000000; i++) prefix[i] = (ll)i*(i+1)/2;
	
	int N;
	cin >> N;
	
	ll s=0;
	ll e=1;
	int ans = 0;
	
	while(e<=N){
		ll len = e-s;
		ll val = s*len + len*(len+1)/2;
		
		if(val == N) ans++;
		if(val <= N) e++;
		if(val >  N) s++;
	}
	
	cout << ans;
	return 0;
}