파이썬 알고리즘-15 (탐색)수들의 합

jiffydev·2020년 8월 26일
0

Algorithm

목록 보기
16/92
post-thumbnail

15.수들의 합
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 = list(map(int, input().split()))
lst=list(map(int, input().split()))

total=0
cnt=0

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

당연히 시간초과로 틀렸다. 연속된 범위에서 합을 구하는 것이므로 일정 이상의 범위는 결국 필요한 합보다 당연히 커지는데, 이를 고려하지 않고 모든 경우의 수를 다 구했으니 걸리는 시간은 기하급수적으로 늘어난다.

풀이

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)

(내가 까먹을 것 같으므로)풀이에 대한 설명: 우선 합이 m보다 작으면 합의 범위가 늘어나야 하므로 rt번째의 값까지 더해주고(rt는 초기값이 이미 lt보다 하나 큰 상태) rt는 한 칸 오른쪽으로 움직인다.그런데 rt가 무한히 커질 수는 없으므로 수열의 개수보다 커지면 break로 빠져나온다.
또한 위에서 설명했던 것처럼 일정 범위 이상의 합은 구할 필요가 없으므로, lt에서 시작한 뒤 rt까지의 합이 m보다 크면 그 다음부터는 합에서 lt 위치의 값을 빼고 lt는 한 칸 오른쪽으로 옮겨준다.
그리고 lt와 rt의 값이 같아지는 경우(=겹치는 경우)는 결국 그 자리의 숫자만 합에 들어가는 것 뿐, 그 합에 따라 다음 움직임이 결정된다.
lt는 합이 커질 때만 오른쪽으로 움직이므로, lt가 rt보다 커지는 경우는 없다.

반성점

  • 중첩된 반복문을 쓰면 속도가 떨어진다는 것은 알고 있었지만, 이를 해결하기 위한 방법이 전혀 떠오르지 않았음.

배운 것

  • 연속된 범위의 (양수의)합 & 그 합이 특정 숫자와 크기 비교해야 하는 경우, 모든 경우의 수를 구하지 말고 특정 숫자와의 비교를 통해 그 이상은 구하지 않아도 된다.
profile
잘 & 열심히 살고싶다

0개의 댓글