[백준/JAVA] 1806_부분합

백준🔗

1806번: 부분합

 

 

문제

 

 

간단 풀이

부분합을 구하는 방법으로, 입력을 받을 때 배열에 누적합으로 저장해서

(i번째 ~ j번째 숫자까지의 부분합) =  (j번째 누적합) - (i-1번째 누적합) 

이렇게 계산했다. 

 

조건(부분합이 S 이상이면서 길이가 최소)을 만족하는 구간을 찾기 위해서는 어제 푼 문제들과 동일한 원리로 이분탐색을 사용했다. 

 

🔗2023.06.07 - [알고리즘/백준] - [백준/JAVA] 2467_용액

🔗2023.06.07 - [알고리즘/백준] - [백준/JAVA] 2473_세 용액

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		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()); // 연속된 수들의 부분합이 S 이상이 되어야 함

		int[] nums = new int[N + 1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			int num = Integer.parseInt(st.nextToken());
			if (num >= S) { // 길이 1로 S 이상이 되는 경우
				System.out.println(1);
				return;
			}
			nums[i] = nums[i - 1] + num; // 누적합
		}
		
		// S 이상의 합을 만드는 것이 불가능한 경우
		if (nums[N] < S) {
			System.out.println(0);
			return;
		}

		int min = N; // 최소 길이
		for (int i = 0; i < N; i++) {
			int start = i + 1;
			int end = N;
			int mid = 0;
			while (start <= end) {
				mid = (start + end) / 2;
				if (nums[mid] - nums[i] >= S) {
					end = mid - 1;
					min = (mid - i < min) ? mid - i : min;
				} else {
					start = mid + 1;
				}
			}
		}
		System.out.println(min);
	}
}

 

참고 자료