백준 1806번 (java) 누적합, 투포인터

---

백준 1806번: 부분합 JAVA

---

관찰

부분합인 것 부터 누적합을 이용해야 할 것 같다는 느낌이 온다!
그리고 연속된 부분합을 구하는 문제이기 때문에 투포인터를 사용해서 시작과 끝을 관리해서 합이 넘으면서 최소의 길이를 찾으면 될 듯?

누적합 + 투포인터

---

정답 코드

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

public class Main {
    static int n,s,min;
    static int[] arr;
    static int[] sumfix;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());
        arr= new int[n+1];
        sumfix = new int[n+1];
        min = Integer.MAX_VALUE;

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            sumfix[i] = i == 1 ? arr[i] : sumfix[i - 1] + arr[i];
        }

        int i = 0;
        int j = 1;
        while(i<=n && j<=n) {
            int sum = sumfix[j] - sumfix[i];
            if(sum < s) {
                j++;
            }
            else {
                if(min > j-i) min = j-i;
                i++;
            }
        }

        if(min == Integer.MAX_VALUE) {
            System.out.println("0");
        }
        else {
            System.out.println(min);
        }

    }


}

---

풀이

배열을 받을 때 누적합을 계산해준다
이제 투 포인터를 활용해서 만약 합이 작으면 j를 늘려 합을 키우고
합이 넘었다면 넘은 값들 중 가장 짧은 것을 찾는다!

자연수만 입력받기 때문에 계속 값이 커지는 게 힌트!
무조건 i,j 둘다 커지기 때문에 200000번의 연산으로 끝난다!

---

생각해 볼 점

자연수가 아니라 음수가 나올 수 있어도 이게 가능할까?

일단 불가능 하다 투포인터는 구간합이 단조 증가하거나 단조 감소하는 경우에 잘 동작한다!

560. Subarray Sum Equals K

이 문제는 구간 합이 정확히 k인 경우를 찾아달라는 것인데 (음수 가능)

누적합을 해시맵으로 저장하면서 풀 수 있다!