[알고리즘] 수들의 합

📌

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i]+A[i+1]+…+A[j-1]+A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

< input example >

 

8 3 #수열 개수, 합의 결과

1 2 1 3 1 1 1 2

 

 

✔️ code

 

import sys
sys.stdin=open("input.txt", "r")

#수열 개수, 합의 결과 
n, m=map(int, input().split())
A=list(map(int, input().split()))
count=0

for i in range(n):
    if A[i]==m:
        count+=1
    for j in range(i+1, n):
        if sum(A[i:j+1])==m:
            count+=1
print(count)

 

>>>

 

sum() 메소드를 사용하여 리스트 부분합으로 문제를 해결했다.

처음에는 범위를 A[i:j] 로 했는데 마지막 두 원소를 계산하지 못해 범위를 A[i:j+1] 로 바꾸어 주었더니,

단독으로 m과 같은 숫자일 경우, 즉 m이 3일 때 원소가 3인 경우를 계산하지 못했다.

따라서 if A[i]==m: 조건문을 j 반복문 전에 적어주어 해당하면 count++ 을 해주도록 만들었다.

 

 

lt=0
rt=0
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)

 

>>>

 

① tot 가 m(수들의 합) 보다 작은 경우

rt < n 이면 아직 리스트 원소를 전부 돈 것이 아니므로,

tot 에 rt 에 해당하는 리스트 value를 더해준다.

그리고 rt 를 1 증가시킨다.

rt > n 이면 리스트 원소를 전부 돈 것이므로,

break 를 통해 종료시킨다.

 

② tot 가 m과 같은 경우

경우의 수를 나타내는 변수인 cnt에 1을 더해주고 tot 에서 lt 에 해당하는 리스트 value를 빼준다.

그리고 lt 를 1 증가시킨다.

 

③ tot 가 m보다 큰 경우

tot 에서 lt 에 해당하는 리스트 value를 빼준다.

그리고 lt 를 1 증가시킨다.