[Python Algorithm] 탐색&시뮬레이션(1차원 리스트 탐색) - 수들의 합

> 탐색 & 시뮬레이션 (1차원 리스트 탐색 편)

 

📖 문제 : 수들의 합

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

 

코드

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 :  # rt를 옮기면서 리스트 모든 항목을 다 거쳤을 경우
                break
        elif tot==m :
    	    cnt+=1
            tot-=a[lt]
            lt+=1
        else : 
    	    tot-=a[lt]
            lt+=1
        
        
print(cnt)

 

 

⭐️ Point ! ⭐️

1차원 리스트 탐색 방법 !

위에서의 tot값은 lt에서 rt전까지의 값들의 합인데,

이 문제에서는 결국 tot값이 주어진 m값과 같으면 cnt값을 +1씩 해주어 cnt값을 구하는 것 !

lt와 rt의 값은 인덱스 값이며 lt값과 rt값을 경우대로 +1씩 값을 증가해 가면서 리스트의 값들을 검사해 나간다.

 

i) tot<m 인 경우

    위의 a 리스트에서 lt=4, rt=6일 때를 보면 

    a[4] = 1, a[6] = 1 , tot = 1+1 = 2

    이때는 rt인덱스값을 1씩 해주어 tot=3이 될 때까지 검사해야한다.

ii) tot==m

    우리가 원하던 값을 찾았다!

    lt=0, rt=3 , a[0]=1, a[3]=1, tot = 1+2 =3

    이때에는 cnt값을 1 증가 시킨후,  a[lt]값을 tot값에서 빼주고, lt+1씩해주어 검사구간을 오른쪽으로 옮겨준다고 생각하면 된다.

iii) tot<m

    ii) 에서 cnt값만 증가시키지 않는 경우이다. 

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이