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()
ps/problems/boj/2015.txt · 마지막으로 수정됨: 2022/07/02 16:31 저자 teferi
토론