[BOJ 1806] 부분합 (Java)

BOJ 1806 부분합

난이도 : 골드 4

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

1806번: 부분합

 

전략

수열의 길이 N이 최대 100,000이므로 당연히 O(N^2)으로 모두 탐색하는 것은 불가능하다.

투 포인터를 이용하여 O(N)에 배열의 연속된 부분합을 탐색할 수 있다.

 

시행착오

처음에는 하나의 loop 안에서 start와 end를 함께 옮기려고 했는데 조건문이 좀 복잡해진다.

따라서 둘 중 하나(코드에서는 start)를 루프의 기준으로 잡고 남은 하나를 가능한 위치까지 옮긴다면

이해하기 쉬운 깔끔한 코드가 나온다

 

코드

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));
        int N, S;
        String[] line = br.readLine().split(" ");
        N = Integer.parseInt(line[0]);
        S = Integer.parseInt(line[1]);
        int[] seq = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++)
            seq[i] = Integer.parseInt(st.nextToken());

        int start = 0;
        int end = 0;
        int sum = seq[start];
        int ans = Integer.MAX_VALUE;

        for (; start < N; start++) {
            while (sum < S && end < N - 1)
                sum += seq[++end];

            if (sum >= S)
                ans = Math.min(ans, end - start + 1);
            sum -= seq[start];
        }

        if (ans == Integer.MAX_VALUE)
            ans = 0;
        System.out.println(ans);
    }
}

end가 0부터 시작하므로 전위증가하였으며, 이에 따라 조건문에서는 N - 2까지만 허용한다.

 

깨달은 점

투포인터를 연습하기 좋은 문제였다.