[BOJ] 1806 부분합 - JAVA

1. 문제

1806번: 부분합

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

---

2. 풀이

누적합을 배열에 저장한다. 이 때, 계산의 편의성을 위해 인덱스는 1부터 시작하도록 한다.

최대값은 N이므로 답은 항상 N+1미만이다. answer을 N+1로 정해두고 만약 탐색이 끝난뒤에도 answer이 N+1이라면 가능한 답이 없으므로 0을 출력해야한다.

오른쪽, 왼쪽을 모두 1로 설정해두고 두 포인터가 모두 N이하일때만 반복하며 탐색한다.

구간의 합이(right-left부분) S보다 크거나 같다면 왼쪽포인터를 옮겨도 된다. 따라서 답을 갱신하고 left+1한다.

S보다 작다면 합을 더 늘려야하므로 right+1하고 다시 반복한다.

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		int N = Integer.parseInt(st.nextToken());
		int S = Integer.parseInt(st.nextToken());

		int[] dp = new int[N+1];
		st = new StringTokenizer(in.readLine());
		dp[1] = Integer.parseInt(st.nextToken());

		for (int i = 2; i <= N; i++) {
			dp[i] = dp[i - 1] + Integer.parseInt(st.nextToken());
		}

		int answer = N+1;
		int left = 1,right = 1;
		while(right<=N){
			if(left>N) break;
			if(dp[right]-dp[left-1] >= S){
				answer = Math.min(answer, right-left+1);
				left++;
			}
			else right++;
		}

		System.out.println(answer==N+1?0:answer);

	}
}

---

3. 결과