[JAVA]백준 1806번: 부분합

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

1806번: 부분합

 

 

 

| 문제 해결방법

 

 

⭐Idea : 투 포인터 알고리즘

 

 

여기서 매번 값을 계산하기 위해 for문을 사용하면 시간초과 난다.

총 합에서 다음 요소를 더해주거나 맨앞의 요소를 빼주는 방법으로 접근.

 

 

유사한 문제 : 백준 2003 수들의 합2 (https://www.acmicpc.net/problem/2003)

 

 

 

[JAVA] 해설 코드

package week11;

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

public class BOJ_1806 {

	static int N, length=100000;
	static long S;
	static int[] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		
		arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			arr[i] =  Integer.parseInt(st.nextToken());
			if(arr[i]>=S) {
				System.out.println(1);
				return;
			}
			
		}
		
		partSum();
		
		if(length==100000) {
			System.out.println(0);	
		}else {			
			System.out.println(length);
		}

	}
	private static void partSum() {

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

			}
		}
		
	}

}

 

 

[제출] 메모리 및 시간