수들의 합

생성일: 2022년 1월 11일 오후 4:58

구현 코드 ⭐

# 수들의 합
import sys
sys.stdin = open("input.txt", "rt")
n, m = map(int, input().split())
l = list(map(int,input().split()))
result = 0

for i in range(0, n):
    sum = l[i]
    j = i+1
    while True:
        if sum == m:
            result += 1
            break
        elif sum < m and j < n:
            sum += l[j]
            j += 1
        else:
            break

print(result)

모범 답안

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:
            break
    elif tot==m:
        cnt+=1
        tot-=a[lt]
        lt+=1
    else:
        tot-=a[lt]
        lt+=1
print(cnt)

차이점

• 내가 구현한 코드에서는 주어진 배열이 클 때 시간초과 오답처리가 되었다.
• why?
  • 나는 이중 반복문을 돌면서 처음 지정된 아이템을 기준으로 연속되는 아이템들을 더했을 때 m보다 커지면 계산했던 값들을 전부 버리고 다시 다음 아이템을 검사하는 방식이기 때문이다.
  • 모범 답안에서는 기준 아이템과 연속되는 아이템들의 합이 m보다 커지면 기준 아이템을 tot에서 빼고 다음 아이템을 기준으로 검사한다. (tot을 버리지 않는다.)
  • 이렇게 하면 동일한 기능을 하면서 시간을 적게 사용할 수 있다.
    • why?
      • 예를 들어, 2 2 3 1 1 2 배열이 주어졌을 때
      • 연속되는 아이템의 합이 5(=m)인 경우를 찾고자 한다면, 처음 기준 아이템을 첫 번째 아이템인 2로 잡게 된다. 그 뒤로 쭉 더하다 보면 tot = 2 + 2 + 3 = 7이 되어서 5를 넘게 되고 해당 기준 아이템은 연속되는 아이템을 더 했을 때 5를 만들 수 없기 때문에 다음 아이템을 기준 아이템으로 잡고 다시 검사해야 한다. 이 때 tot값을 0으로 초기화 하고 다시 반복문으로 확인해도 동일한 기능을 하지만 tot 값에 기존의 기준 아이템인 2를 뺀 값 , 즉, 5를 tot로 유지한 채 다음 기준 아이템을 검사하여도 동일하게 작동한다. 왜냐하면 3번째 자리까지 더하게 된 이유가 그 이전의 아이템들의 합이 5 이하였기 때문인데, 이는 당연히 다음 아이템을 시작점으로 하여 더해 나가도 해당 지점까지는 똑같이 5 이하가 만들어지기 때문이다.