[백준_1806번] 부분합

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

1806번: 부분합

[문제]

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

 

[입력 조건]

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

 

[코드]

import java.util.*;

// 투포인터
public class BaekJoon_1806 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		int n=sc.nextInt();
		int s=sc.nextInt();
		
		int[] num=new int[n+1];
		for(int i=0;i<n;i++)
			num[i]=sc.nextInt();
		
		int min=Integer.MAX_VALUE;
		int start=0;
		int end=0;
		int total=0;
		
		while(true) {
			if(total>=s) { // 조건을 만족하는 경우를 찾았다면 
				total-=num[start]; // 시작지점 앞으로 땡기기
				min=Math.min(min,end-start); // 최소길이 갱신
				start++;
			}
			else if(end==n) // 끝에 도달했다면 while문 종료
				break;
			else // 합이 s 이상이 되기 전까지는 끝 지점을 늘리면서 합 구하기
				total+=num[end++];
		}
		
		if(min==Integer.MAX_VALUE) 
			System.out.println(0);
		else
			System.out.println(min);
	}

}

 

[고찰]

 문제의 시간제한이 타이트한 것을 보고 완전탐색으로 풀면 안된다는 것을 알았지만 어떤 알고리즘을 써야하는지 잘 몰랐다. 그래서 다른 사람의 코드를 참고해보니 많이 풀어보지 않았던 알고리즘 유형 투포인터 문제였다. 스터디 12주차의 주제가 투포인터이기 때문에 여러 문제를 풀어보면서 익숙해져야겠다. 

 투포인터는 말 그대로 배열을 가리키는 포인터를 2개 사용하는 방법이었다. 해당 문제에서 두 개의 포인터를 어떻게 사용할 것이냐를 그림으로 나타내보았다. 

 

이렇게 그림을 그려가며 이해했더니 좀 더 쉽게 문제를 풀 수 있었다.