자바(백준) 1806 부분합

오답 노트 & 새로 알게 된 점

해당 문제는 아마 O(N^2)로도 풀 수 있지만 TLE 때문에 안된다.

그래서 O(N)의 방법으로 풀어야하는데, 그것이 두 포인터를 이용하는 것이다.

 

일반적인 두 포인터와 똑같다.

sum은 [ L..R ] 범위에서, 만약 sum이 S보다 크거나 같으면 갯수를 갱신해주고,

아니면 L을 하나씩 늘리면서 해당 L을 빼줘야한다.

 

기본적인 두 포인터를 배웠다면 어렵지 않게 풀 수 있는 문제이다. 

물론 index 접근이 너무 어렵다..

 

---

코드

package TwoPointers;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ1806 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, S;
    static int A[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        S = atoi(st.nextToken());
 
        A = new int[N + 1];
 
        st = new StringTokenizer(br.readLine());
 
        for (int i = 1; i <= N; i++) {
            A[i] = atoi(st.nextToken());
        }
 
        pro();
    }
 
    static void pro() {
        int e = 0, rel = N + 1, sum = 0;
 
        for (int s = 1; s <= N; s++) {
            sum -= A[s - 1];
 
            while (e + 1 <= N && sum < S) {
                sum += A[++e];
            }
 
            if (sum >= S) {
                rel = Math.min(rel, e - s + 1);
            }
        }
 
        if(rel == N+1) rel = 0;
 
        System.out.println(rel);
    }
}