백준 #1806 - [G4] 부분합 : 두 포인터

(python3)

1806번: 부분합

 

가장 직관적으로 생각나는 '모든 부분 수열 탐색' 시에는 시간 초과가 납니다.

연산 횟수가 "1~N 까지의 합" 으로 처리될 수 있으니까 O(N^2) 으로 100,000 * 100,000 이면 0.5초 보다는 훨씬 긴 시간이 필요합니다.

좌우 포인터를 조금 더 똑똑하게 가지고 가면 일반적인 경우 K가 그리 크지 않은 O(KN) 정도까지 연산이 단축될 수 있을 것 같네요

 

아이디어 : 부분 수열을 효과적으로 처리하는 방법

부분수열은 좌나 우로만 (부분 수열 길이를 기준으로) 늘리거나 줄일 수 있습니다. 베이직한 아이디어는 우는 늘리기만 하고 좌는 줄이기만 해도 구하고자 하는 모든 부분 수열을 탐색할 수 있다는 것입니다.

여기서 우리는 부분 수열의 합이 S 이상이 된 딱 그 시점만 주목하고 싶습니다. 합이 S 보다 모자라면 우를 늘리고, S보다 넘치면 좌를 줄이면 딱 그 시점 근처의 모든 부분 수열을 탐색할 수 있게 됩니다.

부분 수열의 최소 길이를 구하고 싶으니 S보다 커진 바로 그때의 길이들을 저장해서 최소 길이를 출력해주면 됩니다.

추가로 부분 수열의 길이의 최솟값은 1이기 때문에 1이 된 순간 일찍 종료시켜 줄 수도 있습니다.

 

코드

def solution(input) : 
    # 입력 받기
    N, S = list(map(int,input().split()))
    M = list(map(int,input().split()))

    lp = 0 # left pointer
    rp = 0 # right pointer
    s = M[rp] # 부분 수열 합
    lmin = [] # 기준을 넘긴 부분 수열의 최소 길이 (목적 달성을 못한 경우를 처리하기 위해 배열을 사용해봤습니다.)
    while True :
        if s >= S : # 부분합이 기준보다 크면
            lmin.append(rp-lp+1)
            lmin = [min(lmin)] # 길이 저장해서 최소 길이 업데이트
            if lmin[0] == 1 : # 1이면 최소길이니까 1 출력 후 종료
                print(1)
                return
            s-=M[lp] # 기준보다 컸으니 왼쪽을 줄여보기 (길이를 줄여서도 기준을 달성 가능한지 확인)
            lp+=1
        else :
            rp += 1 # 부분합이 기준에 못미치면 오른쪽 늘리기
            if rp >= N : # 수열을 넘어가면 종료
                break
            s += M[rp]

    if len(lmin) :
        print(lmin[0])
    else : # 한번도 목적 달성 못했으면 0
        print(0)

solution(input)

 

my solved.ac :

solved.ac