문제 링크

성능 요약

메모리: 23828 KB, 시간: 256 ms

분류

누적 합, 두 포인터

제출 일자

2025년 1월 3일 17:49:59

문제 설명

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

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

풀이

느낀점

• 투포인터 쓸줄 아는 줄 알았는데 아니었다,, 처음에 세그먼트 트리인가 하고 풀다가 너무 복잡해서 포기,,
• 숫자들이 정렬되어있지 않지만, 연속된 수들의 부분합을 구하고 있기에 투포인터가 가능하다.
• 그런데 투포인터를 다루는 조건을 사용하는 스킬이 아직 부족한 것 같다. 너무 오래 헤맸다.
• 조건에 맞을때까지 right증가, 조건에 맞는 동안 left를 증가하면 갱신할 수 있는 길이가 나오는데, 이후 left에서 하나 빼주고 다음 루프를 돌아야 무한루프에 빠지지 않는다. 조건을 잘 정리하자,,,

설계 : 60분

• left, right 포인터 인덱스를 각각 0으로 초기화, min 은 가능한 최대값 +1
• sum이 S보다 작으면 right++하며 sum에 더하기
• 이후 sum - nums[left] 가 S이상일 때까지 left++하며 sum에서 빼기
• 구해진 최소길이를 갱신하고 left++ 처리한 후 다음 루프

코드(Java)

• 구현 시간: 60분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 부분합_1806
 * Date: 2025.01.03
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int S = Integer.parseInt(input[1]);

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

        int min = n+1;
        int left = 0;
        int right = 0;
        int sum = 0;

        while (left <= right && right < n) {
            while (right < n && sum < S) sum += nums[right++];
            while (left < n && sum - nums[left] >= S) sum -= nums[left++];

            if (sum >= S) min = Math.min(min, right - left);

            sum -= nums[left++];
        }

        if (min == n+1) bw.write("0");
        else bw.write(String.valueOf(min));
		bw.flush();
		bw.close();
		br.close();
	}
}