[백준] 1806번 부분합 C++ 코드

코드

#include <iostream>

using namespace std;

int n, s, a[100003], psum[100003], st = 1, en = 1, res = 200004;

int main() {
    cin >> n >> s;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        psum[i] = psum[i - 1] + a[i]; // 부분합 구해주기
    }
	// 투포인터로 구간합 찾기
    while (en <= n) {
        int tmp = psum[en] - psum[st - 1];
        if (tmp >= s) {
            res = min(res, en - st + 1);
            st++;
        } else {
            en++;
        }
    }

    if (res == 200004) res = 0;
    cout << res << '\n';
    return 0;
}

풀이

처음에는 dp인가 했다가, 연속된 구간이고, 구간합을 구하는 문제였기 때문에 투포인터를 떠올렸다. 구간합 배열을 만들어주고 포인터를 옮겨가면서 tmp값이 s보다 크거나 같으면 시작점을 +1 했고 작으면 끝점을 +1했다. 작을 때 끝점을 옮기는 이유는 더 큰 값을 탐색하기 위함이고, 반대의 경우는 더 적은 구간에서 합을 탐색하기 위함이다.

while문 종료에서 많이 헤맸는데, en이 끝까지 왔을 때도 작으면 더 탐색할 필요가 없기 때문에 반복문을 바로 종료해도 된다.

 

참고

배열을 쓸 때 헷갈릴 거 같으면 차라리 1부터 시작하는 게 좋다.