#341 백준 파이썬 [2003] 수들의 합 2

https://www.acmicpc.net/problem/2003

 

SOLUTION

1) 단순히 1부터 N까지 Sum한 것에서 1부터 K까지 Sum한 걸 빼주면 되는 경우의 수가 있고

2) 투 포인터 알고리즘을 활용해 푸는 방법이 있다. (하단 링크 참조)

전자의 경우엔 수가 작을 경우엔 풀리지만 어느 정도 수가 커지면 시간 복잡도가 N^2가 되기에 비효율적인 단점이 있다.

 

아래의 경우엔 1) 단순하게 풀이하였다.

투포인터로 푸는 방법은 https://claude-u.tistory.com/393를 참고하면된다.

PYTHON CODE

#pypy로 풀이하였음

N, M = map(int, input().split())
A = list(map(int, input().split()))
sum_A = [0] * (N + 1)
#먼저 0~n까지의 합을 구해줌
for i in range(1, N + 1):
    sum_A[i] = sum_A[i-1] + A[i-1]  

answer = 0
#j까지의 합 - i까지의 합으로 구해줌
for i in range(N):
    for j in range(i+1, N+1):
    
    	if sum_A[j] < M: #sum_A[j]가 너무 작아서 해당 수를 만들 수 없는 경우
        	pass
        elif sum_A[j] - sum_A[i] > M: #sum_A[j]가 너무 커서 벗어난 경우
            break
        elif sum_A[j] - sum_A[i] == M:
            answer += 1
            break
            
print(answer)