[C++] 백준 2737번: 연속 합 - Math

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

2737번: 연속 합

 

연속되는 자연수의 합으로 해당 정수를 표현할 수 있는지 묻는 문제

당연히 임의의 자연수를 i라고 하면, 연속하는 자연수이므로 i + 1, i + 2, ... 와 같이 연속된 자연수의 합으로 

정수 N을 표현해야 한다.

 

먼저 자연수 2 개로 N을 표현할 수 있는지 생각해보면,

연속이 시작되는 자연수 (가장 작은 자연수)를 i라고 가정하고, 

i + (i + 1) == N이 되어야 하므로

( N - 1 ) % 2i == 0 이 되어야 한다.

또한, N - 1 != 0이므로 N > 1이라는 조건도 들어가 있다.

 

먼저 자연수 3 개로 N을 표현할 수 있는지 생각해보면,

연속이 시작되는 자연수 (가장 작은 자연수)를 i라고 가정하고, 

i + ( i + 1 ) + ( i + 2) == N이 되어야 하므로

( N - 3 ) % 3i == 0 이 되어야 한다.

또한, N - 3 != 0이므로 N > 3이라는 조건도 들어가 있다.

 

만약 연속된 자연수를 i - 1, i, i + 1로 설정해도 계산은 달라지지 않는다.

이는 3i == N이라는 계산을 유도하는데,

i - 1은 자연수이므로 i > 1이라는 조건이 딸려온다.

즉, 각각의 i에 대해 1보다 크므로 N은 3보다 크다는 조건이 생기게 된다.

(앞서 했던 방식은 i > 0이라는 조건)

 

자연수 2개와 3개로 연속된 자연수의 합으로 N을 표현할 수 있는지 생각해보니,

이를 일반화시켜 조금 더 간단하게 볼 수 있을 것이다.

 

먼저 자연수 2개일 때 N > 1,

자연수 3개일 때 N > 3,

자연수 4개일 때 i, i + 1, i + 2, i + 3 이므로 N > 6 ...

이렇게 나아가므로 

결국 자연수 k개에 대해 N > sum[1, k] + k를 만족하고, 

N % k == 0을 만족해야한다.

 

#include <iostream>
using namespace std;
int main(){
    int n, t; cin >> t;
    while(t--){
        cin >> n;
        long long i=2, r=1, cnt=0;
        while(1){
            if(n<=r) break;
            if((n-r)%i==0) cnt++;
            r+=i, i++;
        }
        cout << cnt << "\n";
    }
}

 

위 코드에서 자료형을 long long을 써준 이유는

sum(1, k)를 계산한 결과를 변수 r에 저장하는데,

이 과정에서 N의 범위가 2^31-1이므로 int 범위를 벗어날 수 있기 때문이다.