[Algorithm][투 포인터] 백준 1806 - 부분합

알고리즘 분류

 투 포인터

 

시간 복잡도

 \( O(N) \)

 

문제 링크

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

---

 이번 문제의 알고리즘 종류는 투 포인터입니다. 주어진 배열에서 조건을 만족하는 연속된 수들 중 가장 짧은 길이를 알아야 합니다. 문제의 제목은 부분합이지만 실제로 이 문제를 푸는데 지난번에 다뤘던 부분합 알고리즘이 사용되진 않습니다. 왜냐하면 부분합 알고리즘은 각 지점마다 누적된 합을 구해놓고 특정 구간의 합만 구하면 되지만 이번 문제는 조건을 만족하는 모든 구간을 알아봐야하기 때문입니다.

 

 투 포인터의 핵심은 "배열이 끝날 때까지 크면 줄이고 작으면 늘린다"입니다. 투 포인터는 배열을 처음부터 탐색하게 되는데 특정 구간의 시작점을 나타내는 S와 끝 지점을 나타내는 E가 있습니다. S부터 E까지의 합을 문제의 조건과 비교하여 크면 부분합을 줄이기 위해 S를 +1 합니다. 반대로 조건보다 작다면 부분합을 늘리기 위해 E를 +1 합니다. 하지만 주의할 점은 E를 +1하기 전에 배열의 끝까지 탐색을 했는지 체크를 먼저 해야합니다.

 

 문제에 따라 투 포인터 알고리즘이 다양한 형태로 사용될 수 있지만 이번 문제는 가장 기본적인 문제입니다. 배열을 처음부터 위에서 말한 방식대로 검사해서 최소 길이만 구하면 됩니다. 부분합 조건을 15라고 가정했을 때 아래의 예시를 통해 흐름을 확인하겠습니다.

 

 시간은 부분합을 최대로 길게 늘인 후 다시 최소로 줄이는 경우 또는 늘리기와 줄이기를 번갈아가며 진행하는 경우가 가장 최악의 경우입니다. 하지만 이 경우에도 2N만큼의 탐색 시간이므로 시간 복잡도는  \( O(N) \)입니다.

 

Java

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int t = sc.nextInt();
        int[] arr = new int[100000];

        for(int i=0; i<n; i++)
            arr[i] = sc.nextInt();

        int s=0, e=0, sum=0, ans=987654321;
        while(true){
            if(sum >= t){
                ans = Math.min(ans,e-s);
                sum -= arr[s++];
            }
            else if(e >= n) break;
            else sum += arr[e++];
        }

        System.out.println(ans==987654321 ? 0 : ans);
    }
}

 

C++

#include <iostream>
using namespace std;

int N,S;
int arr[100000];

int main() {
    cin >> N >> S;
    for(int i=0; i<n; i++) cin >> arr[i];
    
    int s=0,e=0,sum=0,ans=987654321;
    while(1){
        if(sum >= S){
            ans = min(ans,e-s);
            sum -= arr[s++];
        }
        else if(e == N) break;
        else sum += arr[e++];
    }
    
    cout << (ans==987654321 ? 0 : ans);
}