BOJ - 1806 ) 부분합

 

---

 

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

1806번: 부분합

---

역시 이어서 투포인터 유형1번문제이다.

 

https://algorithmstudy-mju.tistory.com/120

BOJ - 2003 ) 수들의 합 2

위에 유형을 좀 정리해놓았다.

 

배열의 처음에 시작하여 목표숫자가 넘으면 개수를 세고, 그때의 s번째의 숫자를 빼준다.

 

다음 루프에서 목표숫자보다 작다면, e번째숫자를 더해준다.

 

위 작업을 반복하고, e가 맨마지막에서 목표숫자보다 클경우, 작을때까지 계속 빼주면서 

 

사용된 숫자개수중 최소를 찾아간다.

 

---

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

public class Main {

	public static void main(String[] args)  throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int t = 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 sum = num[0];
		int cnt = 1;
		int answer = 100001;
		for(int s=0,e=0 ;;) {
			
			if(sum < t) {
				e++;
				if(e==n) break;
				cnt++;
				sum+=num[e];
				
			} else if(sum >= t ) {
				answer = answer > cnt ? cnt : answer;
				cnt--;
				sum-=num[s];
				s++;
				if(e==n-1) {
					while(sum>=t) {
						answer = answer > cnt ? cnt : answer;
						cnt--;
						sum-=num[s];
						s++;
					}
				}
			}
		}
		System.out.println((answer = answer ==100001 ? 0 : answer ));
	}
}

---