๐Ÿ“– [๋ฐฑ์ค€์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ’€์ด] Q.2003 ์ˆ˜๋“ค์˜ ํ•ฉ 2 ํ’€์ด ํˆฌ ํฌ์ธํ„ฐ ๋ฐฉ์‹ - java

๐Ÿ“– ๋ฌธ์ œ

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

N๊ฐœ์˜ ์ˆ˜๋กœ ๋œ ์ˆ˜์—ด A[1], A[2], โ€ฆ, A[N] ์ด ์žˆ๋‹ค. ์ด ์ˆ˜์—ด์˜ i๋ฒˆ์งธ ์ˆ˜๋ถ€ํ„ฐ j๋ฒˆ์งธ ์ˆ˜๊นŒ์ง€์˜

ํ•ฉ A[i] + A[i+1] + โ€ฆ + A[j-1] + A[j]๊ฐ€ M์ด ๋˜๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

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

Q.2003 ์ˆ˜๋“ค์˜ ํ•ฉ 2 ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

i๋ฒˆ์งธ ์ˆ˜๋ถ€ํ„ฐ j๋ฒˆ์งธ ์ˆ˜๊นŒ์ง€์˜ ์—ฐ์† ๋œ ํ•ฉ์ด M์ด ๋˜๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

์—ฌ๊ธฐ์„œ i๋ฒˆ์งธ ์ˆ˜๋ถ€ํ„ฐ j๋ฒˆ์งธ ์ˆ˜๊นŒ์ง€ ์—ฐ์† ๋œ ํ•ฉ์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๋ฏ€๋กœ

๋ˆ„์ ํ•ฉ์„ ์ด์šฉํ•ด์„œ ์‰ฝ๊ฒŒ ํ’€์ด๊ฐ€ ๊ฐ€๋Šฅํ–ˆ์Šต๋‹ˆ๋‹ค.

๋ˆ„์ ํ•ฉ์„ ๊ตฌํ•˜๋Š”๋ฐ ๊นŒ์ง€๋Š” O(N) ์‹œ๊ฐ„๋งŒ์— ๊ฐ€๋Šฅํ•˜์ง€๋งŒ

์ด ๋ˆ„์ ํ•ฉ์„ ์ด์šฉํ•ด ๊ฐ๊ฐ์˜ i๋ฒˆ์งธ๋ถ€ํ„ฐ j๋ฒˆ์งธ๊นŒ์ง€์˜ ํ•ฉ์„ ๊ตฌํ•˜๋Š” ๋ฐ๋Š”

์ด์ค‘ for๋ฌธ์œผ๋กœ O(N^2)์˜ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฌ๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

์ด๋ฅผ ์ข€ ๋” ํšจ์œจ์ ์œผ๋กœ ํ’€์ดํ•  ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์ด ์žˆ์Šต๋‹ˆ๋‹ค.

๋ฐ”๋กœ two pointer ๋ฐฉ์‹์ž…๋‹ˆ๋‹ค.

ํˆฌ ํฌ์ธํ„ฐ ๋ฐฉ์‹์€ ์ด๋ฆ„ ๊ทธ๋Œ€๋กœ ๋‘๊ฐœ์˜ ํฌ์ธํ„ฐ๋ฅผ ๊ฐ€์ง€๊ณ 

์‹œ์ž‘์ ๊ณผ ๋์ ์œผ๋กœ ๋‘ฌ์„œ ํ’€์ดํ•˜๋Š” ๋ฐฉ์‹์„ ๋งํ•ฉ๋‹ˆ๋‹ค.

์ด ํˆฌ ํฌ์ธํ„ฐ ๋ฐฉ์‹์„ ์ด์šฉํ•˜๋ฉด

o(N) ์‹œ๊ฐ„๋งŒ์— ๋‹ต์„ ์‰ฝ๊ฒŒ ๊ตฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

Q.2003 ์ˆ˜๋“ค์˜ ํ•ฉ 2 ๋ฌธ์ œ ๊ฐ™์€ ๊ฒฝ์šฐ์—๋Š”

๋ชจ๋‘ ์ž์—ฐ์ˆ˜๋กœ ์ด๋ฃจ์–ด์ ธ์žˆ๊ธฐ ๋•Œ๋ฌธ์—!

m๋ณด๋‹ค ํ•ฉ์ด ์ž‘๋‹ค๋ฉด end๋ฅผ (๋ ์ง€์ ) ํ•˜๋‚˜์”ฉ ๋Š˜๋ ค์ฃผ๋ฉฐ ์ˆ˜๋ฅผ ๋” ํ•ด์ฃผ๋ฉด ๋˜๊ณ 

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

์‰ฝ๊ณ  ๋น ๋ฅด๊ฒŒ i (start) ๋ถ€ํ„ฐ j (end) ๊นŒ์ง€์˜ ํ•ฉ์ด ๋˜๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ

๊ตฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๐Ÿ’ป ์ฝ”๋“œ


package problem.twopointer;

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

public class Main_2003 {
    static int n,m;
    static int numbers[];
    static int count = 0;


    public static void main(String[] args) throws IOException {
        input();
        solve();
        System.out.println(count);
    }

    public static void solve(){
        int p1,p2;
        int sum = 0;
        p1 = 0;
        p2 = 0;

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

    }


    public 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 March 9, 2021