[1806] 부분합

🔗 문제 링크

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

🔍 문제 설명

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 합을 만드는 것이 불가능하다면 0을 출력한다.

⚠️ 제한사항

• $(10 ≤ N < 100,000), (0 < S ≤ 100,000,000)$

• 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

🗝 풀이 (언어 : Java)

이중 반복문으로 풀었지만 시간초과 판정을 받았다. 이 문제는 투포인터로 푸는 문제였다. 이런 문제를 몇번 풀어봤지만, 아직도 낯설고 접근하기가 까다로웠다. 키 포인트는 첫번째 원소로 도는 반복문은 이중 반복으로 다 돌고, 두번째 원소부터는 첫번째 원소가 끝까지 도달했던 오른쪽 위치를 저장해서 거기서 부터 시작하면 된다는 점이었다. 두번째 원소의 인덱스 ~ 첫번째 원소의 정답 위치까지는 훑어보지 않아도 그 사이값들로만 누적합을 하면 절대 s를 넘지 못한다. 누적합을 보관하는 변수를 만들어주고 바로 전의 원소를 매 반복문마다 빼주어서 누적합을 갱신한다. 누적합이 s보다 크면 최소 길이인지 판별해서 갱신한다.

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

class Main {
    private int findShortest(int n, int s, int[] nums) {
        // 정답 길이의 최대 가능한 값은 n이므로, 성립 안되는 경우 판별을 위해 초기값을 n+1
        int min = n+1, right = 0, sum = nums[0];
        for (int i = 0; i < n; i++) {
            // 첫기준 시작 케이스는 전 순서의 숫자를 누적합에서 빼주는게 아님
            if (i != 0)
                sum -= nums[i-1];
            // 오른쪽에 더할 수가 더이상 없거나, 이미 s보다 누적합이 클때까지 더하기
            while (right + 1 < n && sum < s) {
                right++;
                sum += nums[right];
            }
            // 합계가 s보다 크다면 길이 최소값 갱신, 위에서 s보다 작아도 수를 다 더해서 내려오는 것 예외처리
            if (sum >= s)
                min = Math.min(min, right-i+1);
        }
        return (min == n+1) ? 0 : min;
    }

    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()), s = Integer.parseInt(st.nextToken());
        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
        int[] nums = new int[n];
        for (int i = 0; i < n; i++)
            nums[i] = Integer.parseInt(st2.nextToken());
        br.close();
        Main main = new Main();
        System.out.println(main.findShortest(n, s, nums));
    }
}