[Java/백준/투포인터] 1806번: 부분 합

문제

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

1806번: 부분합

연속된 수들의 부분합들 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성해야 한다.

 

 

참고한 부분은 아래 링크!

https://dev2som.tistory.com/135

[Java] 투 포인터(Two Pointers), 구간 합(Prefix Sum)

제목만 보면 구간 합을 참고했을 것 같지만 투포인터를 참고했다. 이유는 "합이 특정한 수" 이상이 되는  "가장 짧은 구간의 길이"를 구해야하기 때문이다.

 

위의 투포인터 코드를 따르되,

* 구간이 기존의 만족하는 구간 길이(answer)보다 작거나 같아야 한다.

* 아예 만족 못하는 경우가 있기 때문에 boolean 형의 flag를 만든다. flag가 false인 경우에는 만족하는 경우가 하나도 없다는 뜻이므로 0을 출력하게 한다.

를 새로 추가해주었다.

 

끗

 

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));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		int S = Integer.parseInt(st.nextToken());
		
		int answer = N;
		
		int[] arr = new int[N];
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int end = 0, sum = 0;
		boolean flag = false;
		for(int start = 0; start < N; start++) {
			while(sum < S && end < N && end-start <= answer) {
				sum += arr[end];
				end++;
			}
			if(sum >= S) {
				flag = true;
				answer = Math.min(answer, end-start);
			}
			
			sum -= arr[start];
			
		}
		if(!flag)
			answer = 0;
		System.out.println(answer);
		
		br.close();
	}

}