백준 1806

1.문제이해

요약 : 길이 N의 수열의 연속된 수들의 부분합에서 그 합이 S 이상이 되면서 가장 짧은 부분합 길이를 출력

ex) N = {5, 10, 7, 4} 이고 S=15 일때, 5 + 10 or 10 + 7 + 4의 부분합을 구할 수 있음

연속된 수들이기 때문에 부분합은 두 개 이상의 연속된 수로 이루어져야 함

2.문제분석

S이상이 되는 부분합을 체크하고 그 부분합의 길이가 가장 짧은 부분합 길이(minLength)라면 해당 길이로 변경

로직

1. st, en 두 개의 커서를 배열의 시작 지점부터 한 칸씩 오른쪽으로 늘리면서 2개 이상의 수의 부분합으로 이루어져 있는가?

2. 부분합이 S 이상인가?

2.1. S이상이라면 부분합의 길이가 minLength 작은가?

2.1.1. minLength 보다 작다면 minLength값을 변경 후

en 커서를 오른쪽으로 늘릴 필요가 없기 때문에 st커서를 오른쪽으로 한 칸 이동

2.1.2. minLength 보다 크다면 st 커서만 오른쪽으로 한 칸 이동

(en 커서를 오른쪽으로 한 칸 이동하면 부분합 길이가 더 커지기 때문)

2.2. 부분합이 S보다 작으면 en 커서를 오른쪽으로 한 칸 이동
(S보다 커야되는 조건을 찾아야 되기 때문에 부분합 길이를 증가시킴)

3. st, en 커서 둘 중에 하나라도 N의 크기를 넘기면 반복문 종료

4. 반복문 종료 후 minLength의 초기값이 변하지 않았다면 부분합이 없는 경우이므로 minLength에 0을 넣어준다.

5. minLength 출력

3.코드

#include <iostream>
using namespace std;

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

    // 입력 
    int N, S;
    cin >> N >> S;    
    int* arr = new int[N];
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    // 로직    
    int st = 0;
    int en = 0;
    int partSum = arr[0]; // 부분합 초기값     
    int minLength = 0x7fffffff; // 가장짧은 부분합 길이 초기값     

    while (st < N && en < N) {
        // 두 개의 커서 위치를 뺏을 때 1이상인 경우 2개 이상의 부분합으로 이루어져있다는 뜻        
        if (partSum >= S && en - st > 0) {
            if (en - st + 1 < minLength) {
                minLength = en - st + 1;
            }                
            partSum -= arr[st];
            st++;                
        }
        else {
            en++;
            if (en != N) partSum += arr[en];
        }                
    }

    // minLength의 값이 변경되지 않았다면 부분합이 한번도 만들어지지 않았다는 뜻이므로 0을 넣어줌
    if (minLength == 0x7fffffff) minLength = 0;
    cout << minLength;


    return 0;
}