[Baekjoon Online Judge] 1806. 부분합 (C++, Java)

 

핵심

가장 단순한 방법인 3중 반복문을 이용하는 방법은 O(N^3) (시간초과)

 

누적합과 투 포인터 알고리즘에 대해 알고 있다면 쉽게 떠올릴 수 있다.

이 두 개념을 활용하면 시간복잡도가 O(N)으로 줄어든다.

 

두 포인터가 부분 수열의 양 끝을 가리키고 (부분 수열의 합이 S보다 커야한다는) 조건에 맞게 포인터를 조절한다.

 

앞 인덱스가 뒷 인덱스를 역전할 때까지 반복

1. 부분 수열의 합이 S보다 작다면, 크거나 같아질 때까지 뒷 인덱스를 1 증가시키고 해당 인덱스에 해당하는 원소를 추가한다.
2. 조건에 부합하는 최소 부분 수열의 길이를 갱신한다.
3. 부분 수열의 합이 S보다 크거나 같다면, 앞 인덱스에 해당하는 원소를 빼고 1 증가시킨다.

Code (C++)

#include <bits/stdc++.h>
using namespace std;
#define MAX_N 100000

int N, S;
int arr[MAX_N];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> S;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	int i = 0, j = 1, min_len = 0x7fffffff, sum = arr[0];
	while (i < j) {
		if (sum >= S) {
			min_len = min(min_len, j - i);
			sum -= arr[i++];
		}
		else {
			if (j == N) break;
			sum += arr[j++];
		}
	}
	if (min_len == 0x7fffffff)
		min_len = 0;
	cout << min_len;
}

 

Code (Java)

import java.io.IOException;
import java.util.Scanner;

public class Main {

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

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int S = sc.nextInt();

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        int sum = arr[0], mn = Integer.MAX_VALUE;

        int i = 0, j = 0;
        while (i <= j) {
            while (sum < S && j < N - 1) {
                sum += arr[++j];
            }
            if (sum >= S) {
                mn = Math.min(mn, j - i + 1);
            }
            sum -= arr[i++];
        }

        if (mn == Integer.MAX_VALUE) {
            mn = 0;
        }
        System.out.println(mn);
    }
}