[c++] 1806번: 부분합

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

1806번: 부분합

 

문제 요약

 

10,000 이하의 자연수로 이루어진 수열(길이 N)

연속된 수들의 부분합 중 그 합이 S 이상이 되는 것 중 가장 짧은 것의 길이 구하라.

 

범위

 

N (10 ≤ N < 100,000)

S (0 < S ≤ 100,000,000)

원소 (10,000이하의 자연수)

 

 

---

 

우선, 범위를 확인해보자.

N의 최댓값은 약 100,000 이고 S는 1,00,000,000 이다.

S 이상의 부분합이 되는 수열의 길이를 구하는 것이므로 길이는 N 이하로, int형을 사용해도 된다.

 

부분합의 경우, 어디서 부터 시작해서 어디까지 합할 것인지를 생각해봐야 한다. 이를 위해서 L, R과 같이 범위를 지정해주면 좋다.

처음부터 배열의 끝으로 진행하면서 원소의 값을 더하고 합한 결과가 S 이상이라면 answer 값을 업뎃해주는 것도 좋지만 시간 제한이 0.5인 것을 보아 이렇게 하면 안되는 것 같다. 그래서 좀 더 생각해보니 굳이 계속해서 처음부터 더할 필요가 없다는 것을 깨달았다.

 

//N=10 S=15

     L               R
     5   1   3   5  10   7   4   9   2   8
sum  5   6   9  14  24 


         L           R
     5   1   3   5  10   7   4   9   2   8
sum      1   4   9  19


             L       R
     5   1   3   5  10   7   4   9   2   8
sum          3   8  18


...

 

이런 식으로 진행되는데,

L = 1 일 때 sum = 24 가 나왔다. 그런데 L = 2 일 때 sum = 19 가 나오는데, 이 값은 지난 L의 값을 sum에서 뺀 것과 동일한다.

그 뒤의 과정에서도 동일한 패턴이 이루어지는데 이를 통해 앞에 이미 계산한 값을 다시 반복해서 계산할 필요가 없다는 것을 알 수 있다! 

 

 

우선 차근차근 해보면

 

배열을 차례대로 올라가는 부분수열의 첫번째 값의 인덱스인 L을 값을 고정시키고, 마지막 값의 인덱스인 R을 증가시키면서 범위를 조절한다. while문을 통해 배열이 끝나지 않았음과 합계가 아직 S을 넘기지 못했다는 조건하에 계속해서 원소를 더해준다. 합계가 S이상의 경우가 아닌 인덱스 R의 값이 배열을 넘어섰을 경우로 while문을 빠져나왔을 경우를 대비해서 조건문으로 sum >= S를 조건을 달아준 뒤, ans(답) 값을 업데이트 시켜준다. (더 작은 길이를 넣어준다)

 

이 문제에는 조건이 하나 있는데, 바로 합을 만드는 것이 불가능하다면 0을 출력하라는 것이다. 그래서 마지막 문장에 ans가 초기값과 동일하다면 0을 출력하는 것으로 작성했다.

 

//1806번: 부분합
#include <iostream>
#include <algorithm>
using namespace std;
int N, S, x[100001];

void input(){
    cin >> N >> S;
    for(int i=1; i<= N; i++) cin >> x[i];
}

void solution(){
    int r = 0, ans = N+1, sum = 0;
    for(int l=1; l<=N; l++){
        sum -= x[l-1];
        while(r+1<=N && sum < S){ //배열이 끝나지 않았고 S이상의 합계가 나오지 않았다는 조건
            sum += x[++r];
        }
        if(sum >= S) //배열이 끝나서 whlie문을 나오는 경우를 대비해서 sum이 S를 넘겼는지 확인
            ans = ans < r-l+1 ? ans : r-l+1; //최소값으로 업뎃
    }
    if(ans == N+1) ans = 0;//N+1 == ans 라는 것은 S를 넘은 합계가 없다는 것으로, 0 출력
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    input();
    solution();
    return 0;
}

 

 

 

어려웠던 문제.. 다른 사람의 코드를 보고 이해한 뒤 다시 내가 풀어 본 문제..

그런데 이렇게 한번 풀어보니까 다음부터는 잘 적용해서 풀 수 있을 것 같다.

 

한번 풀었던 부분을 다시 푸는 것이 아니라 그것을 활용해서 문제를 풀어나간다는 것이 굉장히 매력적이다..!

세상은 넓고 똑똑한 사람은 많다..

재미있는 문제였따.

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!