[백준] 1806 : 부분합 - JAVA, 자바

문제

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

풀이

구간합 문제이다. for문을 여러번 사용하면 시간초과가 나므로 투포인트를 사용해서 풀어야한다!

위의 그림처럼 start와 end의 위치를 조정해서 문제를 풀이하면 된다.

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

public class B1806 {
	static int N, S;
	static int result = 100001;
	static int sum = 0;
	static int start = 0;
	static int end = 0;
	static int nums[];

	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());

		nums = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}

		while (true) {
			if (sum >= S) {
				sum -= nums[start];
				result = Math.min(result, end - start);
				start++;
			} else if (end == N) {
				break;
			} else {
				sum += nums[end++];
			}
		}

		if (result == 100001)
			System.out.println(0);
		else
			System.out.println(result);

	}

}

위에서 아래의 코드를 사용한 이유는

	sum -= nums[start];
	result = Math.min(result, end - start);
	start++;

아래와 같은 계산을 해주기 위해서이다!

결과