[백준 골드 4] 1806번: 부분합

문제

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

1806번: 부분합

 

 

풀이

• 길이 N의 수열에서 연속된 수들의 부분합 중에 S 이상을 만족하는 것 중, 가장 짧은 경우의 길이를 구한다.
• N의 범위는 10 이상 100,000 이하이고 S의 범위는 0 초과 100,000,000 이하이다.

입력되는 N이 많기 때문에 이중 for문을 사용한 풀이는 무조건 시간 초과가 일어난다.

투포인터를 사용하면 일차원 배열 위에서 인덱스가 움직이는 방식이기 때문에, 최악의 경우 제일 마지막 인덱스에서 조건을 만족하는 경우이므로 O(2n)이 된다. 즉, O(n)의 시간복잡도를 기대할 수 있다.

 

일단 변수 N과 S, 그리고 N 크기의 수열로 입력값을 받는다.

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());
int array[] = new int[N];

st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
    array[i] = Integer.parseInt(st.nextToken());
}

 

투포인터에 필요한 포인터 두개와 부분합을 저장할 sum, 그리고 길이를 비교하기 위한 length를 선언한다. 이때 length는 최소값을 구하는 것이기 때문에 Integer.MAX_VALUE로 제일 큰 값로 초기화한다.

int start = 0;
int end = 0;
int sum = 0;
int length = Integer.MAX_VALUE;

 

while문을 사용해서 풀었는데, 처음에는 while문의 조건을 end < N으로 하였다. end가 수열의 끝까지 도달하면 모든 연산이 끝난다고 생각하였기 때문이다. 그러나 S가 10이고 주어진 수열이 [1, 1, 1, 1, 10]인 경우 제일 마지막까지 start가 도달해야 S 이상이라는 조건을 만족하기 때문에 틀린 생각이었다.

while (end < N){
	// 제일 마지막 위치의 수열이 조건을 만족하는 경우, 계산할 수 없다.
}

 

먼저 while문 조건을 true로 만들어 무한 반복을 시킨 다음, 탈출 조건을 만드는 것으로 방향을 잡았다. 그리고 이 조건을 end == N으로 두고 투포인터 연산을 시작하였다.

만약 sum이 S보다 작다면 end 포인터를 한칸씩 움직여 sum의 크기를 키우고, sum이 S보다 커지는 순간 start 포인터를 한칸씩 움직여 sum의 크기를 줄인 다음 연산을 계속하였다. 수열이 모두 음수가 아니고 조건이 단순히 S보다 큰 경우이기 때문에 이러한 연산이 가능하였다.

if (sum >= S) {
    sum -= array[start];
    length = Math.min(end - start, length);
    start++;
} else if (end == N) {
    break;
} else {
    sum += array[end++];
}

 

이때 sum >= S를 판단하고 end == N라는 탈출 조건을 판단하였는데, S보다 큰 부분합을 끝까지 계산하기 위함이다.

 

 

전체 코드 (Java)

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());
		int array[] = new int[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}

		int start = 0;
		int end = 0;
		int sum = 0;
		int length = Integer.MAX_VALUE;

		while (true) {
			if (sum >= S) {
				sum -= array[start];
				length = Math.min(end - start, length);
				start++;
			} else if (end == N) {
				break;
			} else {
				sum += array[end++];
			}

		}

		System.out.println(length == Integer.MAX_VALUE ? 0 : length);
	}

}

 

 

후기

포인터가 수열의 끝까지 움직여서 부분합을 구할 수 있도록 하는 조건을 찾는데 고생하였던 문제이다. 비슷한 문제를 풀어보면서 연습이 필요할 것 같다.