2018. 수들의 합 5

문제링크 : https://www.acmicpc.net/problem/2018

< 입력 >

정수 N(1<=N<=10,000,000)

< 출력 >

정수 N을 연속된 자연수의 합으로 나타낼 수 있는 경우의 수

< 풀이 >

연속된 수의 합이라는 점에서 등차수열을 이용했다.

5+6+7+8은 1+2+3+4+5+6+7+8에서 1+2+3+4를 뺀 값이라는 점이다.

즉, 1~8까지의 등차수열에서 1~4까지의 등차수열을 뺀 값이다.

그래서 n이라는 수를 받아서 n/2 +1까지를 탐색하며

해당 수(i)까지의 등차수열의 합이 원래의 수(N)보다 크거나 같은지를 확인한다.

그리고 크거나 같을 경우 N과의 차이를 구한다.

이렇게 구해진 N이 1~A(자연수) 까지의 등차수열의 합으로 만들 수 있는 숫자라면

i까지의 등차수열에서 A까지의 등차수열을 뺀 값이 N이라는 것을 알 수 있다.

N의 최대값이 10^7이므로 더했을 때 int의 범위를 넘어갈 수 있다는 점은 주의할 것 !!

---

- 소스 코드 -

/*
 * 시간복잡도 : O(N)
 * 공간복잡도 : O(1)
 * 
 * 연속된 숫자의 합이라는 성질을 이용했습니다.
 * 특정 수 n의 절반+1까지 탐색을 하며 지금까지의 합에서 n을 뺀 값이
 * 등차수열을 만족하는 경우를 찾아서 count를 늘려줬습니다.
 * 마지막에 +1하는 부분은 자기 자신의 경우입니다.
 * 5 + 6 + 7 + 8은 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8에서 1 + 2 + 3 + 4를 뺀 값이라는
 * 성질을 이용했습니다.
*/
#include<iostream>
#include<math.h>
 
using namespace std;
 
typedef long long ll;
 
int main(void){
    ll n;
    cin>>n;
 
    int count=0;
    
    for(int i=1;i<=n/2+1;i++){
        ll temp=((ll)i*(ll)(i+1))/2; // 1부터 i까지의 합
        if(temp-n>=0){ // 합이 주어진 수 n보다 크거나 같다면
            ll myT=(ll)sqrt((temp-n)*2); // 차이가 n*(n+1)/2를 만족하는 자연수 n이 존재하는지 확인합니다.
            if(1ll*myT*(myT+1)==1ll*(temp-n)*2){ // 만약 존재한다면 count++
                count++;
            }
        }
    }
    if(n==1||n==2){
        cout<<1<<endl;
        return 0;
    }
    cout<<count+1<<endl;
}
 

---