[백준BOJ] 1806번 부분합.java

 

백준 저지에서 부분합을 자바를 통해 풀어 보았다. 

 

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

1806번: 부분합

1806번 부분합.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

1806번 부분합

문제

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

설명

이 문제를 브루트포스로 풀게되면 시간 초과에 걸리므로 시간을 단축시키는 다른 방법을 떠올려야한다. 부분합 문제는 투포인터에서 대표적인 문제이다.

 

C언어에서 포인터란 어떤 변수나 배열 등의 주소를 말한다. 투포인터의 포인터도 비슷한 의미로 위치라고 생각하면 된다. 예를 들어 배열에서 포인터라면 어떤 원소의 인덱스이다. 

 

배열에서 연속되는 수들의 부분 배열을 얻을 수 있다. 부분 배열의 양 끝을 start와 end라는 포인터(인덱스)로 표시한다. 이를 통해 부분 배열의 총 합인 부분합을 구한다. end가 1 증가되면 부분합에서 end에 할당되는 배열 값을 더해주고 start가 1증가되면 부분합에서 start에 할당되는 배열 값을 빼준다. 

 

부분합이 S보다 작다면 S보다 큰 부분합을 위해 end를 1증가시키고, 부분합이 S보다 크다면 가장 짧은 길이를 구하기 위해 start를 1증가시킨다. 투포인터를 활용하면 브루트포스보다 훨씬 적은 양의 연산으로 답을 구할 수 있다.

코드

//1806번 부분합.java
package week11;

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

public class 부분합_1806 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    
    public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int S = Integer.parseInt(st.nextToken());
		
		int[] num = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		
		int answer = 100000;
		boolean check = false;
		
		int start=0;
		int end=0;
		int now=num[0];
		while(start<=end) {
			if(now>=S) {
				if(answer > end-start+1) {
					answer = end-start+1;
					check = true;
				}
			}
			if(now<=S && end<N-1) {
				now += num[++end];
			}
			else {
				now -= num[start++];
			}
		}
		
		if(check) {
			System.out.println(answer);
		}
		else {
			System.out.println(0);
		}
	}
}