사용자 도구

사이트 도구


ps:problems:boj:2015

수들의 합 4

ps
링크acmicpc.net/…
출처BOJ
문제 번호2015
문제명수들의 합 4
레벨골드 4
분류

누적합

시간복잡도O(n)
인풋사이즈n<=200,000
사용한 언어Python
제출기록45664KB / 168ms
최고기록156ms
해결날짜2022/07/02

풀이

  • A[i]부터 A[j]까지의 부분합은 A[0]부터 A[j]까지의 누적합에서 A[0]부터 A[i-1]까지의 누적합을 뺀 값과 같다.
  • 따라서 원래 배열에서 부분합이 K인 구간을 찾는 것은, 누적합 배열에서 차이가 K인 두 원소를 찾는것과 동일하다. 이는 간단하게 O(n)에 구현 가능

코드

"""Solution code for "BOJ 2015. 수들의 합 4".

- Problem link: https://www.acmicpc.net/problem/2015
- Solution link: http://www.teferi.net/ps/problems/boj/2015

Tags: [Prefix sum]
"""

import collections


def main():
    N, K = [int(x) for x in input().split()]  # pylint: disable=unused-variable
    A = [int(x) for x in input().split()]

    counter = collections.defaultdict(int, {0: 1})
    answer = 0
    p_sum = 0
    for a_i in A:
        p_sum += a_i
        answer += counter[p_sum - K]
        counter[p_sum] += 1

    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
C U​ S U W
 
ps/problems/boj/2015.txt · 마지막으로 수정됨: 2022/07/02 16:31 저자 teferi