문제 / *수들의 합/ 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을 넘지 않는 자연수이다.

 

▣ 출력설명

 

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

 

▣ 입력예제 

 

8 3 1 2 1 3 1 1 1 2

 

▣ 출력예제 

 

5

---

나의 풀이

n,m = map(int,input().split())

A = list(map(int,input().split()))

cnt = 0


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

print(cnt)

입출력결과

 

출력결과는 답이 맞는데 중첩for문으로 해서 계속 오류가 난다

while문으로 작성하는 연습을 하자..

 

모범답안

n, m=map(int, input().split())
a=list(map(int, input().split()))
lt=0
rt=1 
#tot는 lt부터 rt 전 인덱스값가지의 합을 구하기 위한 변수이다.
tot=a[0] #tot의 시작부분 
cnt=0
while True:
    if tot<m:
        if rt<n:
            tot+=a[rt]
            rt+=1
        else:
            break #tot<m이고, rt가 n번 다 수행하였을 경우 break해준다.
    elif tot==m:
        cnt+=1
        tot-=a[lt] #해당 lt값을 빼주고 증가시켜준다.
        lt+=1
    else:
        tot-=a[lt] #tot가 m보다 크면 해당 값을 빼준다.
        lt+=1 그리고 증가
print(cnt)

 

lt와rt를 설정하여 수들의 합을 구한다.

lt는 수의 합을 더하기 위해 시작지점을 설정해준 변수이다.

rt는 수의 범위를 지정해준다. rt의 전 인덱스까지 더해야한다는 것을 의미한다.

tot는 lt~rt-1인덱스 까지의 합을 나타낸다. lt는 rt와 위치가 같아질 순 있지만 lt가 rt를 넘어설 순 없다.

 

---

※ 알아야 할 것

- 중첩for문은 쓰지 않는다.