[이진탐색] 백준 1806번: 부분합 / 골드 4

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

1806번: 부분합

import sys
input = sys.stdin.readline
n, s = map(int, input().split())
lst = list(map(int, input().split()))


if lst[0] >= s:
    print(1)
    quit()

for i in range(1, n):
    if lst[i] >= s:
        print(1)
        quit()
    lst[i] += lst[i-1]

min_len = sys.maxsize

def bsearch(target, i):
    if lst[-1] < target:
        return sys.maxsize

    left = i + 1
    right = len(lst) - 1
    while left <= right:
        mid = (left + right)//2
        if lst[mid] < target:
            left = mid + 1
        elif lst[mid] > target:
            right = mid - 1
        else:
            return mid - i

    for j in range(left, len(lst)):
        if lst[j] > target:
            return j - i

    return sys.maxsize

min_len = min(min_len, bsearch(s, -1))
for i in range(n):
    target = s + lst[i]  # s = target - lst[i]
    min_len = min(min_len, bsearch(target, i))

if min_len == sys.maxsize:
    print(0)
else:
    print(min_len)

투 포인터로 쉽게 풀리는 듯 했으나 여러 반례를 잡지 못해 좀 오래 걸렸다.

 

0 출력 해주는 것을 안만들어줘서 1차 시도 실패

답이 1인 경우 즉, 원소 하나만 체크 해보는 것을 안해줘서 2차 시도 실패

문제를 s 이상이 아니라 딱 s가 되는 부분수열 길이를 찾는 걸로 짰다는 걸 뒤늦게 발견, 3차 시도 실패

부분 수열이 0번째 원소를 포함하는 경우, 즉 코드상 아래에서 9번째 줄을 안넣어줘서 4차 시도 실패

그리고 성공(2000ms)

좀 더 개선하여 성공(178ms)