[백준] 1806번 부분합

 

 

문제

소스코드

#include<iostream>
#include<vector>
#include<algorithm>
constexpr int MAX_LANGE = 99999999;
 
int main() {
    int N{ 0 }, S{ 0 };
    std::vector<int> v;
    std::cin >> N >> S;
 
    int value{ 0 };
    for (int i = 0; i < N; ++i) {
        std::cin >> value;
        v.emplace_back(value);
    }
 
    int minLange{ MAX_LANGE }, left{ 0 }, right{ 0 }, total{ 0 };
 
    total = v[right];
    while (true) {
 
        //합계가 더 크다면 left 증가
        if (total >= S) {
            minLange = std::min(minLange, right - left + 1);
            total = total - v[left++];
        }
 
        //합계가 더 작다면 right 증가
        else {
            right++;
            if (right == N) {
                break;
            }
 
            total = total + v[right];
        }
    }
 
    if (minLange == MAX_LANGE)
        std::cout <<0;
    else
        std::cout << minLange;
 
}

 

 

후기

이 문제를 해결하기 위한 키워드는 투 포인터(Two Pointer)이다.

 

먼저 주어진 수열을 탐색할 Left Right 포인터 두 개를 만들고 탐색을 시작한다. Total의 값이 주어진 S보다 작다면 right 값을 증가시키면서 Total값을 증가시키고 어느 순간에 Total 값이 S보다 커졌다면 Left값을 하나씩 증가시키면서 가장 짧은 구간을 찾는 문제이다.

 

이 문제에서 가장 조심해야 하는것은 S와 같은걸 찾는 게 아니라 S 이상을 찾는 것이다. 이 때문에 조금 고생했다.  투 포인터는 느끼는 거지만 값이 범위 밖을 벗어나지 않도록 신경 쓰는 게 일인 거 같다.

 

 

문제 게시판에 있던 반례들

10 10 
1 1 1 1 1 1 1 1 1 1 1
답:10
==============
10 10
3 3 3 3 3 3 3 3 3 3
정답: 4
==============
3 2
1 3 1
정답: 1
==============
5 10
1 2 3 4 5
정답: 3
==============
10 2
1 1 1 1 1 1 1 1 1 1
정답: 2
==============
10 100
98 1 1 1 50 50 1 1 1 98
정답: 2
==============

 

 

출처 및 레퍼런스

문제 링크: https://www.acmicpc.net/problem/1806

 

관련 글

[온라인 코딩/탐색(Search)] - [백준] 2003번 수들의 합 2

[온라인 코딩/탐색(Search)] - [백준] 2018번 수들의 합 5