[BOJ][Python][실3][2003] 수들의 합 2

문제 링크

문제링크

첫 번째 풀이

정답 코드

부분합이 m이 되는 구간의 갯수를 찾는 문제입니다. left와 right는 0으로 시작합니다. s = [left,right]의 합입니다.

1. s == m 일때는 ans += 1, right += 1
2. s < m 일 때는 right += 1, s+= arr[right]
3. s > m 일 때는 s -= arr[left], left += 1

left<=right 조건을 만족하면서 증가하기 때문에 $O(n)+O(n) = O(n)$의 시간복잡도를 가집니다.

항공대 알고리즘 소학회 천수환님의 투 포인터 강의는 여기에서 확인하실 수 있습니다 ^^7

import sys
from math import sqrt, ceil
from bisect import bisect_left, bisect_right
from operator import itemgetter

# sys.stdin = open("input.txt", "r")
# dp = [[[0] * K for _ in range(C)] for _ in range(R)]
# MOD = 1000000000
n, k = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
left, right = 0, 0

s = arr[0]
ans = 0
while True:
    if s == k:
        ans += 1
        right += 1
        if right == n:
            break
        s += arr[right]
    elif s < k:
        right += 1
        if right == n:
            break
        s += arr[right]
    else:
        s -= arr[left]
        left += 1

print(ans)

Success Notice: 수고하셨습니다.