백준_부분 합_1806

1. DP (부분합)

 

2. for문을 돌면서 하나씩 더해감

 -> 더해온 값이 S보다 클경우

     S보다 작아질 때 까지 0번 인덱스부터 증가해가면서 빼기. 

 

3. 더 하고 뺄 때 cnt를 증가하고 감소시켜 최소값을 구함.

package baekjoon;

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

public class 부분합_1806 {

	static int N, S, 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());
		}
		
		int sum = 0;
		int ans = Integer.MAX_VALUE;
		int cnt = 0;
		int start = 0;
		for(Integer a : arr) {
			sum+=a;
			cnt += 1;
			if(sum >= S) {
				if(ans > cnt) ans = cnt;
				
				while(true) {
					sum-=arr[start++];
					if(sum < S) {
						cnt--;
						break;
					}else {
						cnt--;
						if(ans > cnt) ans = cnt;
					}
				}
			}
		}
		
		System.out.println(ans == Integer.MAX_VALUE ? 0:ans);
		
	}

}

※  배열의 앞으로는 더하고 뒤로는 빼는 식으로 구현함.  시간복잡도가 n*n 이면 시간초과가 날 수 있는 문제임.