[BOJ] 1806번 부분합 (Python)

Kyeongmin·2023년 7월 24일
0

알고리즘

목록 보기
23/24

📃 문제

[BOJ] 부분합 🔗링크

주어진 수열에서 연속된 수들의 부분합 중 S 이상인 값을 구하는 문제이다.
연속된 수라는 조건 때문에, 투 포인터를 이용해 쉽게 풀 수 있었다.

연속된 수라는 조건이 없었더라도,
정렬 후에 동일하게 투 포인터를 적용하면 풀 수 있을 것 같다.


🧠❓ 문제 접근 및 풀이

🐶 1번째 접근

완전탐색 O(n2)O(n^2) 으로 모든 수의 조합을 확인해서도 풀 수 있는 문제이지만,
투 포인터 개념을 이용해서 O(n)O(n) 으로 풀 수 있었다.

수열 AstA_{st} 부터 수열 AenA_{en} 까지의 합 tt를 구해
SS와 비교한다면 아래 2가지 경우의 수가 나오게 된다.

각 경우의 수마다 아래와 같은 동작을 하면,
모든 숫자의 조합을 확인하지 않고 O(n)O(n) 으로 문제를 풀 수 있다.

t<St < S : tt 를 증가시키기 위해 Index enen 값을 증가시킨다.
tSt \geq S : 현재 부분수열의 길이를 저장하고, tt 를 감소시키기 위해 Index stst 값을 증가시킨다.
단, 2번 조건을 만족하면서 부분수열의 길이가 1인 경우 탐색을 중지한다.
(부분수열의 최소 길이는 1이기 때문)

import sys
input = sys.stdin.readline

def solve():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))

    ans, st, en, t = [], 0, 0, 0
    for en in range(N):
        t += A[en]

        while t >= S:
            if st == en:    return 1
            ans.append(en-st+1)
            t -= A[st]
            st += 1
    return 0 if len(ans) == 0 else min(ans)

print(solve())

profile
개발자가 되고 싶은 공장장이🛠

1개의 댓글

comment-user-thumbnail
2023년 7월 24일

좋은 글 감사합니다. 자주 올게요 :)

답글 달기