[Silver IV] 수들의 합 2 - 2003 (python)

문제 링크

성능 요약

메모리: 32140 KB, 시간: 484 ms

분류

브루트포스 알고리즘, 누적 합, 두 포인터

제출 일자

2024년 6월 22일 03:16:54

문제 설명

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을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

 

 

첫 번째 코드 - 실패

n, m = map(int, input().split())
nums = list(map(int, input().split()))

for i in range(n-1):
    if nums[i] < m:
        for j in range(i+1, n):
            nums[i] += nums[j]
            if nums[i]>=m:
                break

print(nums.count(m))

외부 루프는 n-1번 반복되며, 내부 루프는 최악의 경우 n번 반복된다.

이로 인해 내부 루프에서 부분합을 계산하기 위해 nums[i]에 nums[j]를 더하는 작업을 수행하는데,

전체 시간 복잡도는 O(n^2)에 가깝게 된다. 

그로인한 시간 초과로 실패

 

 

두 번째 코드 - 성공

n, m = map(int, input().split())
nums = list(map(int, input().split()))

l, r = 0, 1
ans = 0
while r <= n and l <= r:

    total = sum(nums[l:r])

    if total == m:
        ans += 1
        r += 1
    elif total < m:
        r += 1
    else:
        l += 1

print(ans)

l과 r은 각각 윈도우의 왼쪽과 오른쪽 경계를 나타내며

total을 계산할 때마다 nums[l:r]의 합을 계산하고, 그 값이 m과 비교하여 포인터를 이동합니다.

이 과정은 리스트의 각 요소를 한 번씩만 방문하므로 전체 시간 복잡도는 O(n)으로 성공!