1806번: 부분합(C++, Kotlin)

제한사항

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

문제 정리

수열의 부분 합이 S 이상이 되야 한다.

Sum(a, b) ≥ S

a ~ b 길이가 가장 짧은 값을 구하시오.

접근 방법

투포인터로 누적합을 통해 조건을 체크하면서 푼다.

// 의사코드
N, S;
array[N];
left = 0;
right = 0;
currentSum = array[0];
minLength = INT32.MAX_VALUE

while (left <= right) {
		if (currentSum >= S) {
				minLength = minLength > right - left + 1 ? right - left + 1 : minLength;
				currentSum -= array[left];
				left++;
		} else {
				right++;
				if (right >= N) {
						break;
				}
				currentSum += array[right];
		}
}

return minLength == INT32.MAX_VALUE ? 0 : minLength;

예외를 생각해보자.

일단, 입력값에 양끝단인 N = 10, S = 0인 경우.

복잡도

시간복잡도 : O(N)

코드

[C++]

#include "iostream"
#include "vector"

using namespace std;

int N, S;

int main() {
    int answer = 0;
    cin >> N >> S;
    vector<int> numbers;
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        numbers.push_back(num);
    }

    int left = 0;
    int right = 0;
    int currentSum = numbers[0];
    int minLength = INT32_MAX;

    while (left <= right) {
        if (currentSum >= S) {
            minLength = minLength > right - left + 1 ? right - left + 1 : minLength;
            currentSum -= numbers[left];
            left++;
        } else {
            right++;
            if (right >= N) {
                break;
            }
            currentSum += numbers[right];
        }
    }

    answer = minLength == INT32_MAX ? 0 : minLength;
    cout << answer;
    return 0;
}

[Kotlin]

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val answer: Int
    val (n, s) = readLine().split(" ").map { it.toInt() }
    val numbers = readLine().split(" ").map { it.toInt() }.toIntArray()

    var left = 0
    var right = 0
    var currentSum = numbers[0]
    var minLength = Int.MAX_VALUE

    while (left <= right) {
        if (currentSum >= s) {
            minLength = minLength.coerceAtMost(right - left + 1)
            currentSum -= numbers[left]
            left++
        } else {
            right++
            if (right >= n) {
                break
            }
            currentSum += numbers[right]
        }
    }

    answer = if (minLength == Int.MAX_VALUE)  0 else  minLength
    println(answer)
}