새소식

Computer Science/코딩테스트 문제 풀이

[백준] [파이썬] [투 포인터] 1806번: 부분합

  • -

 

투 포인터 문제집 : https://www.acmicpc.net/workbook/view/8709

 

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

 

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

예제 입력 1

10 15
5 1 3 5 10 7 4 9 2 8

예제 출력 1

2

 


 

입력 범위는 굉장히 크고 시간 제한은 굉장히 짧다. 

 

이전에 2230번: 수 고르기 문제  https://hyundoil.tistory.com/372

랑 비슷하게 생각하면 된다.

 

수열에서 연속된 수들의 부분합 중에

1. 그 합이 S 이상이 되는 것 중,

2. 가장 짧은 것의 길이

 

import sys 
sys.stdin=open('input.txt', 'r')


def solution(A, N, S):
    left, right = 0,0
    add = A[0]
    answer = 1e9

    while left <= right:
        if add >= S:
            answer = min(answer, right-left+1)
            add -= A[left]
            left +=1
        else:                           # 조건에 만족하지 않으면 
            right += 1
            if right < N:               # 아직 오른쪽 화살표가 수열 안에 있으면 
                add += A[right]
            else:                       # 오른쪽 화살표가 수열의 길이를 넘어서면 
                break                   
            
    if answer == 1e9:
        answer = 0
    
    return answer

if __name__ == "__main__":
    N, S = map(int, input().split())

    A = list(map(int, input().split()))

    # 답변 구하기
    answer = solution(A, N, S)

    print(answer)

 

 

 

 

 

Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.