CS/Algorithm
[BOJ/Python] 백준 2003번 - 수들의 합2
sohy
2022. 5. 15. 00:22
백준 #2003 수들의 합 2
2003번: 수들의 합 2
첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.
www.acmicpc.net
import sys
input = sys.stdin.readline
n, m = map(int, input().split()) # n: 수열 수, m: 합이 나와야 하는 값
seq = list(map(int, input().split()))
i, j = 0, 0 # 포인터
cnt = 0 # 경우의 수
while i <= j and j <= n:
now_sum = sum(seq[i:j])
if now_sum == m:
cnt += 1
i += 1
j += 1
elif now_sum < m:
j += 1
else:
i += 1
print(cnt)- 투포인터를 사용하여 리스트의 구간합을 구한다.
- 구간합이 m보다 클 경우, 앞에 있는 포인터(i)를 한 칸 뒤로 옮긴다.
- 구간합이 m보다 작을 경우, 뒤에 있는 포인터(j)를 한 칸 뒤로 옮긴다.
sum을 한 번만 해줬으면 되는데 if문마다 새로 구해서 시간 초과가 계속 났다 😥
