자바 백준 1806번 문제 - 부분합

문제출처 : https://www.acmicpc.net/problem/1806

1806번: 부분합

 

문제 :

 

소스코드 :

import java.util.*;
class Main {
	// 투포인터 알고리즘 + 슬라이딩 윈도우 알고리즘
	public int solution(int n, int s, int[] arr) {
		int lt = 0, sum = 0;
		int answer = Integer.MAX_VALUE;
		for(int rt=0; rt<n; rt++) {
			sum += arr[rt];
			while (sum >= s) {
				answer = Math.min(answer, rt - lt + 1);
				sum -= arr[lt++];
			}
		}
		if (answer == Integer.MAX_VALUE) answer = 0;
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int s = sc.nextInt();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = sc.nextInt();
		}
		System.out.println(T.solution(n, s, arr));
	}
}

 

풀이 : 투포인터와 슬라이딩 윈도우 알고리즘을 적용하면 아주 쉽게 풀리는 문제이다.

lt와 rt 투포인터를 잡고 for문으로 rt값을 이동시키며 연속된 수들의 합이 s를 넘길 경우 lt값을 이동시키며

최소 길이를 Math.min을 통해 구한다.