[ 백준 / C++ ] 2018 : 수들의 합 5

[ 문제 ]

 

2018번: 수들의 합 5 (acmicpc.net)

 

[ 접근방법 ]

 

투포인터 알고리즘을 활용하였다.

 

l은 수열의 시작, r은 수열의 끝에 위치하는 수를 저정한 변수이다.

 

l부터 r 까지의 합을 n과 비교하면서 경우에 따라  l과 r을 1씩 더하면서 진행한다.

 

만약 합이 n보터 작으면 r을 늘려 수열의 합을 늘린다.

만약 합이 n보다 크면 l을 늘려 수열의 합을 줄인다.

만약 합이 n이라면 카운트하고 l과 r을 전부 1씩 늘려준다.

 

시간복잡도는 O(n)으로 빠르게 문제를 풀 수 있다.

 

[ 소스코드 ]

 

#include <iostream>

using namespace std;

int n, l = 1, r = 1, sum = 1, res;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    while (r <= n)
    {
        if (sum < n)
        {
            sum += (++r);
        }
        else if (sum > n)
        {
            sum -= (l++);
        }
        else
        {
            res++;
            sum += (++r);
            sum -= (l++);
        }
    }

    cout << res;

    return 0;
}