N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의
합 A[i]+A[i+1]+…+A[j-1]+A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.
<내 답안>
n, m = map(int, input().split())
list1 = list(map(int, input().split()))
cnt = 0
for i in range(n):
for j in range(i, n):
sum = 0
for k in range(i, j+1):
sum += list1[k]
if sum == m:
cnt += 1
break
print(cnt)내가 푼 방식은 i와 j를 중첩 반복 시키면서 기준값을 정하고, 그 안에서 i~j 사이를 더하는 반복문을 또 넣는 것이였다. 그리고 만약 sum과 m 이 같아지면 cnt를 증가시키고 break를 해서 다시 i 반복문으로 올라오게끔 했다.
내 코드의 문제는 시간 초과였다. 시간 복잡도를 더 효율적이게 작성할 수 있는 것 같은데 내 머리로는 이 방법 밖엔..
<모범답안>
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)해설은 반복문 한 번으로 풀었다. 내 코드가 얼마나 비효율적이게 푼 것이였는지.. 아무튼 while문 안에서 조건을 3개로 나누었다.
tot<m , tot==m, tot>m 으로 나누어 tot<m 이면 rt가 증가하고, tot==m 와 tot<m 이면 lt를 증가하는 방식이다.
처음에는 조건문 tot<m 안에 있는 if-else 조건문에서 else 일 때 왜 break가 되는지 정확히 이해되지 않았지만, 해설을 들으며 생각해보니 tot<m 일 땐 rt가 증가해야 하는데 더이상 증가할 수 없으므로 이 이후로부터는 무조건 m보다 작은 값들이기 때문에 break를 걸고 나오는 것이였다.
도대체 이런 생각은 어떻게 하는건가.. 다들 대다나다..
