[백준 / 골드4] 1806 부분합 (Java)

문제 보기

---

사용한 것

• 연속된 구간의 합들을 효율적으로 계산하기 위한 구간합

---

풀이 방법

• 구간합을 이용하여 O(n)으로 풀이한다.
• arr의 i 번째 인덱스에 i 번째 인덱스 까지의 합을 저장한다.
• l을 -1 부터 r을 0 부터 시작하여 while 문을 수행한다.
  • arr[r] - arr[l]의 값이 S보다 작으면 r 증가 (l == -1이면 0으로)
  • arr[r] - arr[l]의 값이 S 이상이면 answer 교체 후 l or r 증가 (l 증가하면 r과 같아지는 경우는 r 증가)

---

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int N = Integer.parseInt(line[0]);
        int S = Integer.parseInt(line[1]);
        int[] arr = new int[N];
        line = br.readLine().split(" ");
        int sum = 0;
        for (int i = 0; i < N; i++) {
            sum += Integer.parseInt(line[i]);
            arr[i] = sum;
        }

        int l = -1;
        int r = 0;
        int answer = N + 1;
        while (r < N) {
            int num1 = l == -1 ? 0 : arr[l];
            int num2 = arr[r];
            int diff = num2 - num1;

            if (diff < S) {
                r++;
            } else {
                answer = Math.min(r - l, answer);
                if (l + 1 == r) {
                    r++;
                } else {
                    l++;
                }
            }
        }

        System.out.println(answer == N + 1 ? 0 : answer);
    }
}

---