[알고리즘] 부분합

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

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()), S = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int[] sequence = new int[N];
		for (int i = 0; i < N; i++) {
			sequence[i] = Integer.parseInt(st.nextToken());
		}
		
		// 배열 크기 : n
		// 부분합
		// 완전탐색 : 1 * n + 2 * (n-1) + ... + n * 1 <= n ^ 2
		// 부분합 dp : 1 * n + 1 * (n-1) + ... + 1 * 1 <= n ^ 2
		// 더블 포인터 : n
		
		int start = 0;
		int end = -1;
		int sum = 0;
		int minLength = Integer.MAX_VALUE;
		while (end < N - 1) {
			end++;
			sum += sequence[end];
			// 종료 조건
			if (end >= sequence.length) {
				break;
			}
			
			// 갱신 조건
			if (sum >= S) {
				// while 문을 돌며 sum >= S일 때까지 왼쪽 포인터를 올려준다.
				while (start < end) {
					int temp = sum - sequence[start];
					if (temp < S) {
						break;
					}
					sum -= sequence[start];
					start++;
				}
//				System.out.println(start + " " + end + " " + sum);
				minLength = Math.min(minLength, end - start + 1);
			}
		}
		
		if (minLength == Integer.MAX_VALUE) {
			System.out.println(0);
		} else {
			System.out.println(minLength);
		}
	}
}

나의 풀이

- 시간상 완전탐색과 부분합은 불가능

- 연속되어야 한다는 점을 이용해서 투 포인터 채택(TMI: 모든 지점을 훑을 수 있다.) => 시간 복잡도 = O(n)

- 종료 조건과 갱신 조건을 잘 작성해준다.

- 예외 처리를 잘 작성해준다. ex) 15 이상을 찾아야 할 때 만약 단일 원소가 15라면 1이 출력되어야 한다.

- 내가 의도하는대로 동작하는지 다음과 같이 output을 찍어본다.

 

input

10 15
5 1 3 5 10 7 4 9 2 8

output

start: 3 end: 4 sum: 15
start: 4 end: 5 sum: 17
start: 4 end: 6 sum: 21
start: 5 end: 7 sum: 20
start: 6 end: 8 sum: 15
start: 7 end: 9 sum: 19
2

 

input

10 15
5 1 3 5 15 7 4 9 2 8

output

start: 4 end: 4 sum: 15
start: 4 end: 5 sum: 22
start: 4 end: 6 sum: 26
start: 5 end: 7 sum: 20
start: 6 end: 8 sum: 15
start: 7 end: 9 sum: 19
1