백준 g4 1806 부분합 c++

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

1806번: 부분합

 

문제

길이가 N인 수열이 주어지고, 연속된 수들의 부분합이 S 이상이 되는 것 중 가장 짧은 것의 길이 구하기

 

풀이

 

만약 그냥 이중 for문으로 구현해본다면

for i: 0 ~ N-1
	for j: i+1 ~ N-1
    	if sum >= S
        	min 갱신
        else
        	sum += a[j]
            len++

 

이걸 투포인터로 바꿔보기

 

st, en이 주어지고, st ~ en까지 더한다고 생각하자.

 

1) sum >= S 일 때까지 en++

2) 조건 만족하면 st++

 

여기서 고민했던 건 2가지였다.

1. st++하면 새로운 시작점에서 새로운 합이 시작되는 거랑 똑같은데, en의 커서도 --해서 최적값을 찾아야할까?

- en까지 더해서 겨우 S를 넘었는데 st++을 하게 되면 오히려 sum -= arr[st] 이므로 수가 더 작아진다. en--할 필요 없음

2. en이 수열 끝까지 도달한 경우

- 이 다음은 st++로 sum이 줄어드는 일 밖에 없으므로, 그냥 break 해도 됨

- en == N-1일 땐 if sum >= S 에 걸려서 min을 갱신함.

- 반면에 en == N 일 땐 sum이 부족해서 en을 더 더해야하는 상황이라 어차피 답이 될 수 없음.

 

수도 코드

 

while st != N && en != N
	if sum >= S
    	ans 갱신, 
        
        sum -= st빼기
        st++
        len--
    else
    	en++
        sum += en더하기
        len++

 

 

 전체 코드

/*boj g4 1806 부분합*/
#include <iostream>
#define MAXN 100005
using namespace std;

int N, S;
int arr[MAXN];
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> S;
    for (int i = 0; i < N; i++)
        cin >> arr[i];

    int st = 0;
    int en = -1;

    int sum = 0;
    int len = 0;
    int ans = 100010;
    while (st != N && en != N) {
        if (sum >= S) {
            ans = min(ans, len);

            sum -= arr[st];
            st++;
            len--;
            continue;
        } else {
            en++;
            sum += arr[en];
            len++;
        }
    }
    if (ans == 100010) ans = 0;
    cout << ans << "\n";
}