[백준/자바] 1806번: 부분합

문제

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

풀이

• 10,000 이하의 자연수로 이루어진 길이 N짜리 수열
• 이 수열에서 연속된 수들의 부분합 중에 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이 출력
• 만일 합을 만드는 것이 불가능하다면 0을 출력

투 포인터와 누적합을 활용하면 쉽게 풀 수 있는 문제입니다.

입력

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		s = Integer.parseInt(st.nextToken());
		
        // 배열 초기화
		st = new StringTokenizer(br.readLine());
		arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		System.out.println(twoPointer());
	}

• n: 배열의 길이
• s: 부분합

길이 탐색

	static final int INF = 1_000_000_000;
	
	private static int twoPointer() {
		int sum = 0, best = INF, left = -1;
		
		for (int right = 0; right < n; right++) {
			sum += arr[right];
			
			while (left < right && sum >= s) {
				sum -= arr[++left];
				best = Math.min(best, right - left + 1);
			}
			
		}
		
		return best == INF ? 0 : best;
	}

• sum: arr에서 left ~ right의 부분합
• best: 부분합의 길이
• right 인덱스를 늘려가며 누적합을 진행합니다.
• 만약 sum의 크기가 s이상이 될 경우
  • left 인덱스를 늘려줍니다.
  • 그에 대해 best의 크기도 업데이트해 줍니다.
• 이렇게 하면 바라보고 있는 곳의 부분합을 계속해서 구해줄 수 있습니다.
• 마지막에 길이를 구할 수 없을 경우 0, 아닐 경우 best를 리턴해 주었습니다.

코드

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

public class Main {
	static int n, s;
	static int[] arr;
	
	static final int INF = 1_000_000_000;
	
	private static int twoPointer() {
		int sum = 0, best = INF, left = -1;
		
		for (int right = 0; right < n; right++) {
			sum += arr[right];
			
			while (left < right && sum >= s) {
				sum -= arr[++left];
				best = Math.min(best, right - left + 1);
			}
			
		}
		
		return best == INF ? 0 : best;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		s = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		System.out.println(twoPointer());
	}

}