[Python] 수들의 합

[문제]

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

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

▣ 입력예제 1
8 3
1 2 1 3 1 1 1 2

▣ 출력예제 1
5

---

[풀이]

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)

---

[내용]

알고리즘 자체를 이해하지 못했다.

 

<알고리즘 설명>

배열을 기준으로 위치를 나타내는 lt, rt 포인터를 이용한다.

tot 이라는 변수는 a[lt] 부터 a[rt] 이전까지 합한 수를 의미하며, tot 와 m 값을 비교해가며 lt, rt 위치를 변경한다.

tot, m 값 비교	알고리즘 설명
tot < m	tot 값에 a[rt] 값을 더하고,  rt 위치 1 증가
tot == m	cnt 값을 1 증가, tot 값에 a[lt] 값을 빼고, lt 위치 1 증가
tot > m	tot 값에 a[lt] 값을 빼주고, lt 위치 1 증가

 

 

	tot(1) < m(3) tot 값에 a[rt] 값인 2를 더하고,  rt 위치 1 증가
	tot(3) == m(3) cnt 값을 1 증가, tot 값에 a[lt] 값인 1을 빼고, lt 위치 1 증가
	tot(2) < m(3) tot 값에 a[rt] 값인 1을 더해주고,  rt 위치 1 증가
	tot(3) == m(3) cnt 값을 1 증가, tot 값에 a[lt] 값인 2를 빼주고,  lt 위치 증가
	tot(1) < m(3) tot 값에 a[rt] 값인 3을 더해주고,  rt 위치 1 증가
	tot(4) > m(3) tot 값에 a[lt] 값을 빼주고, lt 위치 증가
	tot(3) == m(3) cnt 값을 1 증가, tot 값에 a[lt] 값인 3를 빼주고,  lt 위치 증가
	tot(0) < m(3) tot 값에 a[rt] 값인 1을 더해주고,  rt 위치 1 증가
	tot(2) < m(3) tot 값에 a[rt] 값인 1을 더해주고,  rt 위치 1 증가
	tot(3) == m(3) cnt 값을 1 증가, tot 값에 a[lt] 값인 2를 빼주고,  lt 위치 증가
	tot(2) < m(3) tot 값에 a[rt] 값인 2을 더해주고,  rt 위치 1 증가
	tot(4) > m(3) tot 값에 a[lt] 값을 빼주고, lt 위치 증가
	tot(2) < m(3) 이므로 rt 위치를 증가시켜야 하는데,  마지막까지 처리하고 m번째까지 와있으므로 => break 처리