[백준] 2003 : 수들의 합2 / python

1. 문제 설명

2003번: 수들의 합 2

 

문제

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

 

출력

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

 

2. 풀이 전 계획과 생각

sum (i, j) ⇒ M되는 경우의 수를 일일히 구하면,

 

i를 결정 O(N) 1≤ i ≤ j

j를 결정 O(N) i ≤ j ≤ N

모든 i, j 까지의 합 구하기 O(N)

⇒ O(N^3)라는 시간복잡도가 나온다.

 

 

시간을 줄여보자.

1. 누적합을 구하자. O(N)
2. i를 결정 O(N) 1≤ i ≤ j⇒ O(N^2)
3. j를 결정 O(N) i ≤ j ≤ N
4. 합 sum[j] - sum[i-1]

⇒ O(N^2)

 

 

투 포인터를 사용해서 탐색의 범위를 줄여보자.

1. 누적합을 구하자. O(N)
2. L, R 같은 시작점에서 출발하여 결정하자.
   1. (L, R)의 합이 N보다 작으면 R은 오른쪽
   2. (L, R)의 합이 N보다 크면 L은 오른쪽
   3. (L, R)의 합이 N이면 count 증가, R 오른쪽
   종료조건 : L > R이면 합이 N보다 큰 경우 밖에 없기에 종료,
3. R == N이면 L을 오른쪽으로 해도 합보다 작음으로 종료

⇒ O(N)

 

3. 풀이

length, sum = map(int, input().split())
num = list(map(int, input().split()))
cumulated_sum = [num[0]] * (length)
count = 0

if length >= 2:
    for i in range(1, length):
        cumulated_sum[i] = cumulated_sum[i-1] + num[i]

left, right = 0, 0
while True:
    if left > right or right >= length :   break

    if left == 0:
        prefix_sum = cumulated_sum[right]
    else:
        prefix_sum = cumulated_sum[right] - cumulated_sum[left-1]

    if prefix_sum < sum:
        right += 1
    elif prefix_sum > sum:
        left += 1
    else:
        count += 1
        right += 1

print(count)

• 틀렸습니다.

 

4. 풀이하면서 막혔던 점과 고민

🤔  빠진 경우의 수가 무엇이 있을까?

1 2 3 4 5 6 7 8 9 10

10

11

12

13

14

15

16

17

18

9

L이 오른쪽으로 계속 가야하는데, R도 같이 오른쪽으로 가주지 않아 체크해주지 못하고 종료된다.

L이 오른쪽으로 갈 때, R보다 크면, L이 오른쪽 가고, R도 L의 위치로 가줘야 한다.

 

5. 풀이 후 알게된 개념과 소감

length, sum = map(int, input().split())
num = list(map(int, input().split()))
cumulated_sum = [num[0]] * (length)
count = 0

if length >= 2:
    for i in range(1, length):
        cumulated_sum[i] = cumulated_sum[i-1] + num[i]

left, right = 0, 0
while True:
    if left > right or right >= length :   break

    if left == 0:
        prefix_sum = cumulated_sum[right]
    else:
        prefix_sum = cumulated_sum[right] - cumulated_sum[left-1]

    if prefix_sum < sum:
        right += 1
    elif prefix_sum > sum:
        left += 1
        if left > right and left < length:
           right = left
    else:
        count += 1
        right += 1

print(count)

• 투 포인터를 사용하여, 탐색의 범위를 줄여줄 수 가 있었다.
• 투 포인터가 양끝에서 서로를 향해 이동하는 경우도 있고,
• 투 포인터가 모두 왼쪽으로 시작해서 같은 방향으로 이동하는 경우가 있다.