[코테 한 알] 자료구조 / 투 포인터

1. 투 포인터란 ?

2개의 포인터를 이용하여 구간의 시작과 끝을 제한하는 방식

 

 

2. 투 포인터의 시간복잡도

포인터를 이동하는 계산이 전부이므로, O(n)의 시간복잡도를 가진다.

따라서 큰 수를 다루는 계산에 유리하게 사용된다.

 

 

 

3. 투 포인터 예제

[BOJ 2018]  수들의 합 5

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다.
당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다.
반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

 

 

🌵 Key

1)  N이 엄청 크다 → start_index, end_index 이용한 투 포인터로 풀이

2)  sum = 1, count = 1 초기화 (sum : 현재 연속 구간 합, count : 가짓수)

 

※ 투 포인터 이동 원칙 

sum > N	왼쪽 값 삭제해서 줄이기	sum -= start_index;    start_index++;
sum == N	완성, 오른쪽 늘리면서 다시 탐색	count++; sum += end_index;
sum < N	오른쪽 값 추가해서 늘이기	end_index++; sum += end_index;

 

🍏 Sol

#include <iostream>

using namespace std;

int main() {

    int N;
    cin >> N;

    int start_idx = 1, end_idx = 1;
    int sum = 1, count = 1;

    while(end_idx < N) {
        if(sum < N) {
            end_idx++;
            sum += end_idx;
        }

        else if(sum == N) {
            count++;
            end_idx++;
            sum += end_idx;
        }

        else {
            sum -= start_idx;
            start_idx++;
        }
    }

    cout << count << endl;

    return 0;
}