[백준] 1806번 부분합 자바(Java)

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

 

전형적인 투포인터 문제다.

투포이터는 O(N)의 시간복잡도를 갖는다. 시간제한이 0.5초인 이 문제에 사용하기 딱이다. (사실 자바는 1초 제한.. ㅠ)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        int[] arr = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int left = 0;
        int right = 0;
        int sum = 0;
        int ans = Integer.MAX_VALUE;

        while (right <= N && left >= 0) {
            if (sum >= S) {
                ans = Math.min(ans, right - left);
                sum -= arr[left++];
            } else {
                sum += arr[right++];
            }
        }
        
        if (ans == Integer.MAX_VALUE) {
            ans = 0;
        }
        System.out.println(ans);
    }
}

 

 

 

[기억하자]

투 포인터

- O(n) 의 시간복잡도를 가진다.

- 구간합, 부분합 연산에 사용하기 적합하다.

 

- 이름이 비슷한(?) 이분탐색과는 차이가 크다. 투 포인터는 보통 연속된 구간의 특성을 활용하여 조건을 만족하는 구간을 찾고, 이분탐색은 특정 값을 찾기 위해 많이 사용되는 알고리즘이다.