Algorithm - 수의 합

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[수의 합]

 

N개의 수로 된 수열 A[1], A[2], ... , A[N]이 있다.

 

이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + A[i+2] + ... + 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을 넘지 않는 자연수이다.

 

*출력 설명

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

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_15.txt', 'rt')

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)

 

input_15.txt(입력)

8 3
1 2 1 3 1 1 1 2

 

 

중요내용

1. 변수 lt와 rt는 인덱스 번호를 나타내는 포인트 변수로, 초기 값을 lt = 0, rt = 1로 선언한 것은 포인트 변수로 사용하기 위함이다.
2. 변수 tot는 lt부터 rt 바로 앞 까지의 데이터 총합을 의미한다. (중요)
3. 위의 답안에서 사용된 매커니즘은 tot와 m을 비교하면서, 모든 데이터(요소)의 합을 확인해보는 것이다.
4. 즉, tot >= m이면 lt를 우측으로 옮기고(lt의 인덱스 번호 1만큼 증가), tot < m이면 rt를 우측으로 옮겨서(rt의 인덱스 번호 1만큼 증가) 모든 데이터(요소)의 합을 확인해보는 것이다.