BOJ 1806 - 투포인트

www.acmicpc.net/problem/1806

1806번: 부분합

부분합이지만, 부분합의 원소를 구하는 것이 아니라, 부분합이 S인 최소원소 길이를 구하는 것이라, 투포인트 S, E로 구하면 된다.

 

처음엔 접근이 어려웠으나,.. 풀다 보니.. 조금씩 이해하려 한다.

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

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

        int s=0, e=0, sum = 0, dis=Integer.MAX_VALUE;

        while (true) {
            if(sum >= S){
                sum -= Num[s++];
                dis = (dis > e - s + 1)? e - s + 1 : dis;
            } else if (e == N)
                break;
            else {
                sum += Num[e++];
            }
        }

        if (dis > 100000000)
            System.out.println(0);
        else
            System.out.println(dis);
    }
}