[백준] 1806.부분합 (java) / 투포인터, 슬라이딩 윈도우

@투포인터, 슬라이딩 윈도우 / 14m

설마 진짜 이렇게 하면 풀리나 했는데 진짜였다.

투포인터 개념을 이 글을 보고 공부했는데, 이 방법으로 풀면 바로 풀 수 있다.

투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09)

풀이는 이 글이 훨씬 잘 나와 있으므로 따로 적지 않았다.

 

 

문제 링크

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

1806번: 부분합

 

 

삽질 포인트

만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

이 조건을 못보고 풀어서 틀렸습니다가 떴다.

 

처음에는 long으로 풀어야 되는건가? 라고도 생각했는데,

배열의 최대 길이가 100,000이고, 한 칸의 최대값이 10,000이라

sum의 최댓값이 10억이므로 int형으로도 충분히 가능하다.

 

 

코드

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

public class Main {
	
	static int N, S, arr[];

	public static void main(String[] args) throws Exception {
		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());
		
		System.out.println(slide());
	}

	private static int slide() {
		int s = 0, e = 0, sum = 0, min = N + 1;
		
		while (true) {
			if (sum >= S) sum -= arr[s++];
			else if (e == N) break;
			else sum += arr[e++];
			
			if (sum >= S)
				if (min > e - s)
					min = e - s;
		}
        if (min == N + 1) min = 0;
		return min;
	}
}

 

 

ㅋㅋㅋㅋㅋㅋㅋ

 

끝!