[백준] 1806번 : 부분합

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

1806번: 부분합

해당 문제는 이중 for문으로 문제를 해결 할 수 있다.N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000) 조건이 이므로, 시간복잡도는 O(N^2) 이고, 시간복잡도 문제가 발생한다. 투포인터를 이용하여 O(2N) -> O(N) 의 시간복잡도로 문제를 해결 할 수 있다.

p1과 p2로 포인터를 2개를 두고, p1=0 인상태 p2=1인 상태 그리고 초기 value=arr[0], 초기 length = 1로 두고 출발을 한다.

 

1) 종료시점

종료시점은 p2가 N-1상태이고 value가 S보다 작다면 p1을 움직여봐야 이미 최소 값이기 때문에 종료한다. p2가 N-1 상태에서 value가 S보다 크다면 p1을 N-1 상태까지 움직여서 최소 길이를 구해야하는데 value가 S보다 크다면 p1 커서만 움직여서 최소값을 구하기때문에 종료 조건은 if (N == p2 and value < S or N == p1) 로 잡았다.

 

2) 커서 움직임 조건

Value가 S보다 작은경우

- Value에 arr[p2] 값을 더하고 길이를 1증가 시키고, p2 커서를 하나 증가한다.

Vluae가 S보다 큰경우

- 최적의 길이의 값의 조건이기때문에 최소길이를 갱신한다, 그후 Value에 arr[p1] 값을 빼고, 길이를 1감소시키고, p2 커서를 증가시킨다.

 

INF = int(1e9)
N, S = map(int, input().split()) # N은 수열의개수, S는 부분집합의 합
arr = list(map(int, input().split()))


p1 = 0
p2 = 1
value = arr[0]
currentlen = 1
minlength = INF
while True:
    if (N == p2 and value < S) or (N == p1): # end가 도달했을경우
        if value >= S:
            minlength = min(minlength, currentlen)
        break
    
    if value < S: # 현재 value 값이 부분의 합보다 작다면
        value += arr[p2] # p2 를 더한다
        p2 += 1 # p2를 1증가한다
        currentlen += 1

    else:
        minlength = min(minlength, currentlen)
        value -= arr[p1] # p1 값을 뺀다
        p1 += 1 # p1 값을 더한다
        currentlen -= 1
        

        
if minlength == INF:
    print(0)
else:
    print(minlength)