백준 문제풀이 : (2018) 수들의 합 5 - c/c++

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

2018번: 수들의 합 5

 

시간 제한	메모리 제한	난이도	알고리즘 분류
2초	32 MB	Silver 5	수학 / 두 포인터

 

 

문제

 

 

풀이

자연수 N의 범위가 1부터 10,000,000 까지이기 때문에, 연속된 자연수로 이루어진 집합의 수는 nx(n-1)/2 = 49,999,995,000,000 이며, o(n)의 값이 2초 안에 처리할 수 있는 연산량을 훌쩍 넘어간다. 

 

따라서 반복을 줄일 수 있는 방법을 생각해야 하며, 시간 복잡도 n번 내에 처리할 수 있다면 가장 좋을 것이다.

 

먼저 숫자 N과 합이 N이 될 연속된 숫자들에 대한 당연한 규칙들을 하나씩 정리해보았다.

 

1. 연속된 숫자들 중 최대값은 N/2 값을 넘어가지 않는다.

(N/2를 넘어가는 순간, (N/2)+(N/2+1) 조합이 되어 N 값을 초과해버린다.) 

2. 연속된 숫자들은 맨 좌측 수 부터 맨 우측 수 까지 1씩 증가하는 등차수열이다. 

3. '연속된 숫자들'이기 때문에, 중간에 다른 값이 끼어들거나 수를 건너뛰지 않는다.

 

즉, 마치 기차가 출발하듯 앞의 수를 떼어내고, 뒤의 수를 붙여가며 검사를 해봐도 놓치는 숫자 조합이 없다는 뜻이다.

 

이 발상을 그대로 코드에 활용해 앞에서 숫자를 떼어가는 포인터와 뒤에서 숫자를 붙여가는 포인터 두 가지 변수를 활용한다. 

 

 

코드 작성

#include <iostream>

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    
    int end=1, start=0, count=0; //시작 포인터는 0, 끝 포인터는 1에서 시작.
    int sum=start+end; // 숫자 조합을 end 포인터가 가리키는 '1' 부터 검사 시작.
    
    while(end<=n/2) { // end 포인터는 n/2 값을 넘어갈 수 없다. 
        if ( sum<=n ) { 
            if (sum==n) count++; // sum 값이 n과 같다면 조건에 만족하므로 카운팅
            end++; sum+=end; // sum이 n보다 작다면 숫자를 추가. 
        }
        else { sum-=start; start++; } // sum이 n보다 크다면 숫자를 제거.
    }
    
    printf("%d", count);
}

 

 

END.