[Algorithm/Java] 백준 1806번 - 부분합

---

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

---

🔍 문제 풀이

헷갈린점

처음엔 아래와 같이 while(r < n) 은 r이 배열의 끝에 도달하면 즉시 종료되도록 작성하였다.

while (r < n) {
    if (sum >= s) { ... }
    else sum += arr[r++];
}
// 여기서 끝남 -> 마지막 수축 기회 없음

하지만 r이 n에 도달한 후에도 sum이 s 이상인 상태라면, l을 계속 이동시키며 남은 경우를 모두 확인해야 한다.

따라서 아래처럼 r == n이어도 sum >= s일 때는 먼저 수축을 실행하도록 변경하였다.

while (true) {
    if (sum >= s) {
        ans = Math.min(ans, r - l);
        sum -= arr[l++];
    } else if (r == n) {   // 끝까지 왔으면 그제서야 종료
        break;
    } else {
        sum += arr[r++];
    }
}

sum이 더 이상 조건을 만족 못 할 때 비로소 r == n 분기로 들어가 break 되어 마지막 수축이 실행된다.

또는 아래와 같이 둘 중 하나라도 가능하면 루프를 실행하도록 작성할 수 있다.

while (r < n || sum >= s) { // 하나라도 참이면 반복 유지
    if (sum >= s) {
        ans = Math.min(ans, r - l);
        sum -= arr[l++];
    } else {
        sum += arr[r++];
    }
}

💻 코드

합이 크면 왼쪽 줄이고, 합이 작으면 오른쪽 늘리는 식으로 구간합 구한다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];

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

        int l = 0, r = 0, sum = 0;
        int ans = Integer.MAX_VALUE;

        while(true){
            if(sum >= s) {
                ans = Math.min(ans, r - l);
                sum -= arr[l++];
            } else if(r == n) break;
            else sum += arr[r++];
        }

        System.out.println(ans == Integer.MAX_VALUE ? 0 : ans);
    }
}