[BF] 1806번 부분합

1806번 부분합

 

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

 

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

 

입력

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

 

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

예제 입력

10 15
5 1 3 5 10 7 4 9 2 8

 

예제 출력

2

 

해결방법

1. n개의 부분수열을 탐색하는 경우 → 브루트 포스 (DFS 탐색)
2. 연속된 부분수열을 탐색하는 경우 → Left & Right 탐색

 

 

⭐️ 1차 시도 ⭐️

시간 초과

 

처음에는 브루트포스(DFS+백트래킹)의 방법으로 문제를 풀었다

하지만 당연히 시간초과가 발생했다

백준 강의를 찾던 중, 일부 경우만 해보기 라는 탐색법을 발견했고, 이를 활용해 문제를 다시 풀었다

 

 

⭐️ 2차 시도 ⭐️

맞았습니다!!

 

연속된 부분수열에서 합이 S 보다 큰 경우 중, 가장 작은 길이를 구해야 한다

따라서 수들의 합2 문제와 동일하게 접근하면 된다

선택해야하는 개수가 정해져있지 않고, 연속된 부분수열을 구하는 문제니 Left & Right 탐색을 진행해야한다

• 만약 한 노드에서 다른 모든 노드로의 합을 계산한다면 n개의 노드를 n번 비교해야 하므로 O(n²) 의 시간복잡도가 발생한다

• 하지만 Left & Right 탐색을 수행하면 반복문을 1번 수행하기 때문에 O(n) 의 시간복잡도를 가지게 된다

 

while(L<n && R<n){
    if(sum < m){
        sum += arr[++R];
    }else if(sum == m){
        ans = min(ans, R-L+1);
        sum += arr[++R];
    }else if(sum > m){
        ans = min(ans, R-L+1);
        sum -= arr[L++];
        
        if(L > R){
            R = L;
            sum = arr[L];
        }
    }
}

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 100001
#define INF 987654321
using namespace std;

int n,m;
int L,R,sum,ans;
int arr[MAX];

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }
    
    L = 0;
    R = 0;
    ans = INF;
    sum = arr[L];
    
    while(L<n && R<n){
        if(sum < m){
            sum += arr[++R];
        }else if(sum == m){
            ans = min(ans, R-L+1);
            sum += arr[++R];
        }else if(sum > m){
            ans = min(ans, R-L+1);
            sum -= arr[L++];
            
            if(L > R){
                R = L;
                sum = arr[L];
            }
        }
    }
    if(ans == INF)
        cout << 0 << "\n";
    else
        cout << ans << "\n";
}