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보다 커지는 경우는 없다.
반성점
- 중첩된 반복문을 쓰면 속도가 떨어진다는 것은 알고 있었지만, 이를 해결하기 위한 방법이 전혀 떠오르지 않았음.
배운 것
- 연속된 범위의 (양수의)합 & 그 합이 특정 숫자와 크기 비교해야 하는 경우, 모든 경우의 수를 구하지 말고 특정 숫자와의 비교를 통해 그 이상은 구하지 않아도 된다.
