b1806. 부분합

 

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

 

 

 

이번 문제는 배열에서 연속 부분합이 SSS 이상이 되는 최소 길이를 구하는 문제다.

먼저 배열의 크기 NNN과 목표 합 SSS를 입력받고 배열 arr를 생성한다.
이후 배열의 최댓값을 maximum에 저장하고,
누적 합을 계산할 배열 dp를 초기화한다.
누적 합 배열은 0부터 iii까지의 합을 저장하며,
이를 이용해 특정 구간의 합을 빠르게 계산할 수 있다고 생각했다.

find 메서드는 연속 부분합의 길이를 1부터 NNN까지 늘려가며 모든 구간을 탐색한다.
탐색 중 누적 합이 SSS 이상이 되는 구간이 발견되면 해당 길이를 반환하고 종료한다.
만약 모든 구간을 탐색해도 조건을 만족하는 구간이 없다면 0을 반환한다.
마지막으로 계산된 최소 길이를 출력하며,
이 값이 연속 부분합이 SSS 이상이 되는 최소 길이를 나타내려 했다.

하지만 시간초과가 났고 고민후, 투포인터 알고리즘을 활용할 생각을 하였다.

 

 

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


public class Main {

    private static int N,S,maximum;
    private static int[] arr;
    private static long[] dp;

    private static int find(int start){
        for(int i = start ; i <= N; i++){ //길이
            for(int j = 0 ; j <= N-i ; j++){ // 길이탐색
                if(dp[i+j]-dp[j]>=S) return i;
            }
        }
        return 0;
    }

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

        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        String s = br.readLine();
        arr = Arrays.stream(s.split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        maximum = Arrays.stream(arr).max().orElse(0);
        dp = new long[N+1];
        dp[0] = 0;
        dp[1] = arr[0];

        if(maximum == 0)
            System.out.println(0);

        for(int i = 1 ; i <= N; i++)
            dp[i]=dp[i-1]+arr[i-1];

        System.out.println(find(S/maximum));
    }
}

시간초과 코드

 

 

 

투 포인터 알고리즘을 사용해 효율적으로 조건을 만족하는 최소 길이를 찾아낼 수 있었다.

먼저 입력값을 처리해 배열 arr와 목표 합 SSS를 초기화한다.
이후 minLength를 int Max 값으로 설정하여 최소 길이를 추적하고,
sum과 left를 초기화해 투 포인터 탐색을 시작한다.

right 포인터는 배열의 끝까지 순회하며 현재 구간의 합을 sum에 더한다.
만약 sum이 SSS 이상이 되면, left 포인터를 이동시켜 구간의 길이를 줄인다.
이 과정에서 현재 구간의 길이를 계산해 minLength를 갱신한다.
이후 sum에서 arr[left]를 빼고 left를 증가시켜 다음 구간으로 이동한다.

탐색이 끝나면, minLength에는 조건을 만족하는 최소 길이가 저장된다.
만약 조건을 만족하는 구간이 없다면 minLength는 초기값으로 남아 있으므로 0을 출력하고,
그렇지 않다면 최소 길이를 출력한다.
이 코드는 O(N)의 시간 복잡도를 가져 효율적으로 시간초과 문제를 해결할 수 있었다.

 

 

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

public class Main {

    private static int N, S;
    private static int[] arr;

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

        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        arr = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        int minLength = Integer.MAX_VALUE;
        int sum = 0;
        int left = 0;

        for (int right = 0; right < N; right++) {
            sum += arr[right];

            while (sum >= S) {
                minLength = Math.min(minLength, right - left + 1);
                sum -= arr[left++];
            }
        }

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