[백준 알고리즘]1806번: 부분합_Java

[문제]

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

​

[입력]

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

​

[출력]

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

​

[예제]

 

---

>문제 풀이

​

* 투포인터 문제

주어진 N길이의 배열에 대해 연속되는 숫자의 합이 S이상이 되는 것중 가장 짧은 길이를 구해야합니다.

​

배열에 대해 인덱스를 나타낼 변수 int left=0, right=0를 선언을 해줍니다.

left=0을 기준으로 right를 오른쪽으로 이동해가는데, 이 때 갱신되는 합이 S이상인지 아닌지에 따라 처리를 해줍니다.

오른쪽의 값들을 더해가면 무조건 이전의 sum보다는 sum+arr[right]가 더 큰 값이 됩니다.

​

위의 조건에 주의하며, while문과 함께 포인터들을 조작하여, 최소 길이인 len을 구해줍니다.

​

if ( sum>=S )

len와 right-left+1을 비교하여 더 작은 값으로 len을 갱신해줍니다.

//그리고 left변수를 옮겨줄건데, 그럼 sum에서도 빼줘야하기 때문에

sum-= arr[left++];

​

else //sum<S

//아직 S보다 작은 수이기 때문에 더 더해줘야합니다.

//right변수를 오른쪽으로 옮겨주고 sum에 더해줍니다.

sum+= arr[++right]

​

if ( left와 right범위 체크)

left와 right를 ++ 해줬을 때 범위를 벗어나면 종료시켜야 합니다.

앞에서 arr[N+1]을 해놨기 때문에 +arr[N] 는 정상 동작합니다. 물론 arr[N]값은 0이기 때문에 더했을 때 sum에 영향을 미치지도 않습니다. 하지만 다음 while문을 반복하기 전 계속 left와 right를 조작해도 되는지 범위 체크를 해줘야합니다.

 

 

>전체 코드

 

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

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, S;
		int arr[];
		
		N= Integer.parseInt(st.nextToken());
		S= Integer.parseInt(st.nextToken());
		arr= new int[N+1];
		
		st= new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i]= Integer.parseInt(st.nextToken());
		}
		
		
		int left=0, right=0, sum=arr[0];
		int len=Integer.MAX_VALUE;
		
		while(left<N&&right<N) {
			if(sum<S) {
				sum+=arr[++right];
			}else {
				len= Math.min(len, right-left+1);
				sum-=arr[left++];
			}
			if(left>=N||right>=N) break;
		}
		
		if(len==Integer.MAX_VALUE) len=0;
		System.out.println(len);
	}
}

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

1806번: 부분합