[BOJ] 백준 1806번 부분합 (Java)

#1806 부분합

난이도 : 골드 4

유형 : 투 포인터

1806번: 부분합

▸ 문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

▸ 출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

문제 풀이  

전형적인 투 포인터 문제이다. 투 포인터는 인덱스를 가지고 노는 문제이기 때문에 항상 범위를 신경써줘야 한다. 부분합과 같은 경우는 타입도 고려해줘야 하는데 해당 문제는 int범위를 초과하지 않아 그냥 int로만 풀어도 된다.

 

내가 잠깐 헤맸던 부분은 역시 배열 인덱스 범위였다. 초기 설정 값으로는 끝 범위까지 도달하지 못하여 75%에서 계속 fail이 떴었다.

• 내가 인덱스를 다루는 방식은 start, end가 0에서 동시에 시작하였다.
• sum < s 이면, sum에  arr[end] 를 더하고 end++를 해주고,
• sum >=s 이면, sum에 arr[start]를 빼고 start++해주었다.

 

문제는 while문이 end>n-1이면 종료하기 때문에 n에 도달하면 종료가 되어 맨 끝 인덱스를 탐색하지 못했다. 반례는 다음과 같다.

10 1101
5 1 3 5 10 7 4 9 100 1000

 

그래서 배열 범위를 1늘려주고 while문 종료 조건도 변경해주었다. 

while(start <= end && end <= n) {
	if(sum < s) {
		sum += arr[end++];
	} else if(sum >= s) {
		len = Math.min(len, end-start);
		sum -= arr[start++];
		
	}  
}

 

설계

1. 배열을 입력받는다. 
2. start, end 투 포인터를 설정하여 탐색한다.
   1. 연속된 부분합 중 s 이상인 구간의 길이를 구한다.
   2. sum < s, 값이 작으므로 end포인터 위치에 있는 배열값을 더해준다. 
   3. sum >= s, 값이 크거나 같으므로 start 포인터 위치에 있은 배열값을 빼준다.
3. 구한 부분합의 길이 중 가장 짧은 길이를 출력한다.

 

풀이 코드 

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

public class Main {
	public static void main(String[] args) throws IOException{
		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[] arr = new int[n+1];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int start = 0;
		int end = 0;
		int len = Integer.MAX_VALUE;
		int sum = 0;
		while(start <= end && end <= n) {
			if(sum < s) {
				sum += arr[end++];
			} else if(sum >= s) {
				len = Math.min(len, end-start);
				sum -= arr[start++];
			}  
		}
		System.out.println(len==Integer.MAX_VALUE ? 0 : len);
	}
}