[BaekJoon] 1806 부분합 (Java)

1.  문제 링크

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

2.  문제

요약

• 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어집니다.
• 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 문제입니다.
• 입력: 첫 번째 줄에 0보다 크거나 같고 100,000보다 작거나 같은 N과 0보다 크고 100,000,000보다 작거나 같은 S가 주어지고 두 번째 줄에 각 원소의 값이 10,000보다 작거나 같은 자연수인 수열이 주어집니다.
• 출력: 첫 번째 줄에 구하고자 하는 최소의 길이를 출력합니다. 만약 그러한 합을 만드느 것이 불가능하다면 0을 출력합니다.

3.  소스코드

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

public class Main {
	static int N, S;
	static int[] seq;
	static int[] ac_sum;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		S = scanner.nextInt();
		seq = new int[N + 1];
		ac_sum = new int[N + 1];
		for(int i = 1; i <= N; i++) seq[i] = scanner.nextInt();
	}
	
	static void accumulate_sum() {
		ac_sum = seq.clone();
		for(int i = 2; i <= N; i++) {
			ac_sum[i] += ac_sum[i - 1];
		}
	}
	
	static void solution() {
		int L = 0, R = 1, len = Integer.MAX_VALUE;
		while(L < R && R <= N) {
			int sum = ac_sum[R] - ac_sum[L];
			if(sum >= S) {
				len = Math.min(len, R - L);
				L += 1;
			} else {
				R += 1;
			}
		}
		System.out.println(len == Integer.MAX_VALUE ? 0 : len);
	}
	
	public static void main(String[] args) {
		input();
		accumulate_sum();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

4.  접근

• 이 문제는 투포인터 및 누적합을 이용하여 구할 수 있는 문제입니다.

accumulate_sum 함수

static void accumulate_sum() {
	ac_sum = seq.clone();
	for(int i = 2; i <= N; i++) {
		ac_sum[i] += ac_sum[i - 1];
	}
}

• 이 함수는 누적합을 구하는 함수입니다.
• seq라는 배열에 주어진 배열을 저장하고 ac_sum이라는 배열에 seq의 각 위치까지 누적하여 더한 값을 넣습니다.

solution 함수

static void solution() {
	int L = 0, R = 1, len = Integer.MAX_VALUE;
	while(L < R && R <= N) {
		int sum = ac_sum[R] - ac_sum[L];
		if(sum >= S) {
			len = Math.min(len, R - L);
			L += 1;
		} else {
			R += 1;
		}
	}
	System.out.println(len == Integer.MAX_VALUE ? 0 : len);
}

• 투포인터를 이용하여 앞에서부터 합이 S가 되는 부분 수열을 구하고 그 길이를 구하여 그 중 가장 짧은 배열의 길이를 구합니다.
• 왼쪽 포인터인 L을 처음에는 0으로, 오른쪽 포인터인 R을 처음에는 1로 하면 수열의 첫 번째 숫자부터 시작할 수 있기 때문에 이를 초기값으로 하고 오른쪽 포인터를 하나씩 늘려가면서 L부터 R까지 숫자의 합을 구합니다.
• 합을 구할 때는 위에서 구한 누적합을 이용하여 R번째에서의 누적합에서 L번째 누적합을 빼서 구합니다.
• 만약 이 합이 S보다 크거나 같다면 조건에 맞기 때문에 이 때의 길이를 구하고 이전의 최소 길이와 비교하여 갱신시킵니다. 또한 여기서 오른쪽 포인터를 이동시키면 S 이상인 값이긴 하지만 길이가 늘어나기 때문에 왼쪽 포인터를 이동시켜 더 적은 길이로 합이 S 이상인 부분 수열을 만들 수 있는지 확인합니다.
• 만약 합이 S보다 작다면 합을 S 이상으로 만들어주기 위해 오른쪽 포인터를 이동시킵니다.