[백준1806] / 부분합 - 투포인터 (!엉성함주의!)

백준1806

 

푼 날짜 : 2024.09.04

푼 문제 : [1806] / 부분합

사용한 언어 : python

 

 

푼 방법 :

투포인터로 접근하였다.

왜냐하면 범위자체가 N (10 ≤ N < 100,000), S (0 < S ≤ 100,000,000), 수열은 10,000이하의 자연수이기 때문에 매번 합을 구하는 것은 비효율적이므로 이전합에 가장 왼쪽 값을 빼주고 오른쪽 값을 더해가는 식의 투포인터로 풀었다.

 

가장 어려웠던 것은 index 계산이었다.

결국... 약간 엉성하게 반례에 맞는 조건을 다시 한 번 걸어줌으로써 문제를 해결했다.

 

예를들면 아래와 같은 반례이다. 

4 2
6 7 8 9

 

이런 경우에는 굳이 합을 구하지 않아도 각각의 원소가 S이상이기 때문에 최소의 길이는 당연히 1이 된다.

 

이번 코드에서는 미리 한 바퀴 돌면서 각 요소가 하나라도 S를 넘는다면 바로 1을 출력하게 하고 아닐경우 투포인터 로직에 들어가게끔 작성했다...  마음에 들지 않는 코드이기에 추후 다시 수정해 볼 필요성을 느끼고 있다.

 

 

코드 :

import sys

N, S = map(int, sys.stdin.readline().split())
lst = list(map(int, sys.stdin.readline().split()))

check = False
for i in lst:
    if i >= S: check = True

if check: print(1)
else:
    i, j = 0, 1
    ans = []
    sum_= sum(lst[:j+1])
    while j < N:
        if sum_ < S:
            if j+1 < N:
                j += 1
                sum_ += lst[j]
            else: break
        else:
            ans.append(j-i+1)
            sum_ -= lst[i]
            i += 1
    print(min(ans) if ans else 0)

 

 

 

반례 정리가 되어있는 백준 링크가 있어 함께 첨부하겠다.

https://www.acmicpc.net/board/view/138214

 

 

더 깔끔하게 풀 수 있는 방법이 있을 것 같다.

추후에 다시 풀어봐야겠다!