[Algorithm] 부분 수열의 합

▶ 문제

N개의 수로 이루어진 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 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
sys.stdin=open("input.txt", "r")
n, m = map(int,input().split())
a = list(map(int, input().split()))

cnt = 0
for i in range(n):
    s = 0
    for j in range(i, n):
        s += a[j]
        if s == m:
             cnt+=1
print(cnt)

수열의 시작 값과 끝 값을 정하기 위해 이중 for문을 사용하였다.

연속된 수열의 값을 구하는 것이기 때문에 두번째 for문의 범위는 첫번째 for문의 값 이상이 되게 설정했다. 

그리고 나서 수열의 값들을 s에 더하였고, 그 더한 값이 m과 같으면 counting을 해주었다. 

처음 생각했을 땐 좀 복잡했는데 코드를 짜보니 의외로 간단했다. 

 

 

▷ 예시 코드

import sys
sys.stdin = open("input.txt", 'r')
n, m=map(int, input().split())
a=list(map(int, input().split()))

lt = 0
rt = 1
tot = a[0]
cnt = 0
while True:
    if tot < m:
        if rt < n:
            tot += a[rt]
            rt += 1
        else:
            break
    elif tot == m:
        cnt += 1
        tot -= a[lt]
        lt += 1
    else:
        tot -= a[lt]
        lt += 1
print(cnt)

이 코드는 해석을 봐도 어려워서 이해하는 데 한참 걸렸다.

좀 길고 복잡하지만 꼭 알고 넘어가야 할 논리인 것 같아 혼자 짤 수 있을 때까지 반복해야 겠다..

 

부분수열 시작 index 값을 lt , 마지막 index 값을 rt로 지정하고 각각 0과 1로 초기화했다. 

tot는 수열의 합을 담아가는 변수이며, 처음엔 index lt 값만 들어가 있는 상태로 초기화했다.  

 

while문 안의 첫번째 조건에서 tot 값이 m보다 작을 경우에는 index rt 값을 tot에 더하고, rt 를 1 증가시킨다. 합이 아직 m보다 적기 때문에 수열의 길이를 늘려가며 확인하기 위함이다. 이 반복은 부분수열의 오른쪽 끝 값인 rt가 n까지 갔을 때 비로소 끝이 난다. 

tot가 m일 경우에는 당연히 정답 카운팅을 하고, index lt의 값을 tot에서 뺀 후 lt 값을 1증가시킨다. 다음 수열을 계속해서 확인하기 위해서는 시작 index값이 오른쪽으로 이동해야 하기 때문이다. 

tot가 m보다 클 경우에도 index lt의 값을 tot에서 빼고 lt를 1 증가시킨다. 합이 더 큰 상황이기 때문에 시작 index 값을 오른쪽으로 옮겨 길이를 줄여가는 과정이다. 

이 조건들이 반복되다 rt가 n까지 넘어가는 순간이 오면 while문이 종료되고, 카운팅한 정답이 출력된다. 

 

다시 정리해 봐도 좀 어렵다...

코드를 보면 알긴 알겠는데 혼자서 이런 생각을 한다는 것은 정말 말도 안된다. 

나중에 미래의 내가 보고 '별 거 아니었네 뭐' 하는 날이 오길.