투 포인터 (수들의 합 5)

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

2018번: 수들의 합 5

N의 최댓값이 10000000으로 매우 크게 잡혀 있으므로

O(N)의 시간 복잡도 알고리즘을 사용해야 한다.

 

이런 경우 자주 사용하는 방법이 투 포인터.

시작 인덱스와 종료 인덱스를 지정하여

연속된 수를 표현한다.

 

배열이 아니다. 1 , 2, 3, 4 ... 실제 값이 인덱스이다.

 

이 문제에서의 투 포인터 이동 방 

sum > N : sum -= start_index; start_index++;

sum < N  : end_index++; sum += end_index;

sum == N : end_index++; sum = sum + end_index; cnt++;

 

#include <iostream>
 
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n;
    cin >> n;
    // n 하나면 1개로 카운트 하므로 ans는 1로 시작
    int ans = 1;
    int start_index = 1;
    int end_index = 1;
    int sum = 1;
 
    while (end_index != n)
    {
        // 답을 찾았을 때
        if (sum == n)
        {
            ans++;
            end_index++;
            sum += end_index;
        }
        // 현재 합이 답보다 클 때
        else if (sum > n)
        {
            sum -= start_index;
            start_index++;
        }
        // 현재 합이 답보다 작을 때
        else
        {
            end_index++;
            sum += end_index;
        }
    }
    cout << ans << '\n';
    return 0;
}