๐Ÿ“– [๋ฐฑ์ค€์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ’€์ด] Q.1806 ๋ถ€๋ถ„ํ•ฉ ๋ฌธ์ œ ํ’€์ด - java

๐Ÿ“– ๋ฌธ์ œ

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

10,000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜๋กœ ์ด๋ฃจ์–ด์ง„ ๊ธธ์ด N์งœ๋ฆฌ ์ˆ˜์—ด์ด ์ฃผ์–ด์ง„๋‹ค.

์ด ์ˆ˜์—ด์—์„œ ์—ฐ์†๋œ ์ˆ˜๋“ค์˜ ๋ถ€๋ถ„ํ•ฉ ์ค‘์— ๊ทธ ํ•ฉ์ด S ์ด์ƒ์ด ๋˜๋Š” ๊ฒƒ ์ค‘, ๊ฐ€์žฅ ์งง์€ ๊ฒƒ์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

๐Ÿ” ์ ‘๊ทผ๋ฒ•

Q.1806 ๋ถ€๋ถ„ํ•ฉ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

๊ธธ์ด๊ฐ€ N์งœ๋ฆฌ์ธ ์ˆ˜์—ด์ด ์ฃผ์–ด์ง€๋Š”๋ฐ ์ด ์ฃผ์–ด์ง„ ์ˆ˜์—ด์—์„œ ์—ฐ์†๋œ ์ˆ˜๋“ค์˜ ๋ถ€๋ถ„ํ•ฉ ์ค‘์—

ํ•ฉ์ด S์ด์ƒ์ด ๋˜๋Š” ๊ฒƒ๋“ค ์ค‘ ๊ฐ€์žฅ ์งง์€ ๊ธธ์ด๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

ํˆฌ ํฌ์ธํ„ฐ๋ฅผ ์ด์šฉํ•˜์—ฌ ํ’€์ด๊ฐ€ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

๋ชจ๋‘ ์ž์—ฐ์ˆ˜๋กœ ์ด๋ค„์ ธ์žˆ์œผ๋ฏ€๋กœ!

S๋ณด๋‹ค ํ•ฉ์ด ์ž‘๋‹ค๋ฉด end๋ฅผ (๋์ชฝ ํฌ์ธํ„ฐ) ํ•˜๋‚˜์”ฉ ๋Š˜๋ ค์ฃผ๋ฉฐ ์ˆ˜๋ฅผ ๋” ํ•ด์ฃผ๋ฉด ๋˜๊ณ 

๋ฐ˜๋Œ€๋กœ S๋ณด๋‹ค ํ•ฉ์ด ์ปค์ง„๋‹ค๋ฉด start๋ฅผ (์•ž์ชฝ ํฌ์ธํ„ฐ) ํ•˜๋‚˜์”ฉ ๋Š˜๋ ค์ฃผ๋ฉฐ ์•ž ์ง€์ ์˜ ์ˆ˜๋ฅผ ๋นผ์ฃผ๋ฉด

์‰ฝ๊ฒŒ ํ•ฉ์ด S์ด์ƒ์ด ๋˜๋Š” ๊ฒฝ์šฐ๋“ค์„ ์ฐพ์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๊ทธ ์ค‘์—์„œ ๊ธธ์ด๊ฐ€ ๊ฐ€์žฅ ์งง์€ ๊ฒฝ์šฐ๋ฅผ ๊ตฌํ•˜๋ฉด ๋‹ต์„ ๊ตฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๐Ÿ’ป ์ฝ”๋“œ


package problem.twopointer;

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

public class Main_1806 {
    static int n, m;
    static int numbers[];
    static int start, end;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        input();
        solve();
        if (min == Integer.MAX_VALUE)
            System.out.println(0);
        else
            System.out.println(min);
    }

    private static void solve() {
        int sum = 0;
        start = 0;
        end = 0;

        while (true) {
            if (sum >= m) {
                sum -= numbers[start++];
            } else if (end == n) {
                break;
            } else {
                sum += numbers[end++];
            }

            if (sum >= m) {
                min = Math.min(min, end - start);
            }
        }

    }


    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String temp[] = br.readLine().split(" ");
        n = Integer.parseInt(temp[0]);
        m = Integer.parseInt(temp[1]);
        numbers = new int[n];
        temp = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(temp[i]);
        }
    }
}

Written on April 25, 2021