백준 1806번 부분합 Java

: ) YOUNG·2024년 2월 13일
1

알고리즘

목록 보기
316/417
post-thumbnail

백준 1806번
https://www.acmicpc.net/problem/1806

문제



생각하기


  • 투 포인터를 활용해 특정 구간의 부분 합을 구하는 문제이다.


동작



결과


코드



import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    // input
    private static BufferedReader br;

    // variables
    private static int N, S;
    private static int[] arr;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        sb.append(twoPointer());
        return sb.toString();
    } // End of solve()

    private static int twoPointer() {
        int start = 0;
        int end = 0;
        int len = Integer.MAX_VALUE;
        int sum = 0;

        while (end <= N) { // end가 N에 도달할 때까지 또는 N+1이 될 때까지 반복
            if (sum >= S) {
                len = Math.min(len, end - start);
                sum -= arr[start++];
            } else if (end == N) {
                break; // end가 배열의 끝에 도달하면 종료
            } else {
                sum += arr[end++];
            }
        }

        if (len == Integer.MAX_VALUE) {
            return 0;
        } else {
            return len;
        }
    } // End of twoPointer()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
    } // End of input()
} // End of Main class

0개의 댓글