728x90
반응형
문제 :
N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의
합 A[i]+A[i+1]+…+A[j-1]+A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …,
A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.
출력
첫째 줄에 경우의 수를 출력한다.
입력 예시
8 3
1 2 1 3 1 1 1 2
출력 예시
5
코드 :
# 수들의 합
import sys
N, M = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
cnt = 0
start, end = 0, 1
tmp = A[0]
while start < N:
if tmp == M:
cnt += 1
tmp -= A[start] # 맞다면 자기 자신의 값 빼서 0를 만듬
start += 1
if end == N and tmp < M:
break
elif tmp < M:
tmp += A[end]
end +=1 # end 증가시킴
elif tmp > M:
tmp -= A[start]
start += 1
print(cnt)
728x90
반응형
최근댓글