[BOJ] 2018 수들의 합 5

https://www.acmicpc.net/problem/2018

어떤 숫자를 주고 그 숫자 이하의 수 중 연속된 수를 합쳐서 해당 숫자가 되는 경우의 수를 구하는 문제이다.

코드 1 - 실패

start, end라는 점을 주고 end까지의 합 - start까지의 합을 통해서 start + 1부터 end까지의 합을 구했고, 이 합이 숫자 n보다 크거나 작음에 따라서 start, end를 이동시켰다.

n = int(input())

start = 0
end = 1

def calSum(i):
  return (i+1) * (i) // 2

ans = 0

while start < end and end <= n:
  if calSum(end) - calSum(start) < n:
    end += 1
  elif calSum(end) - calSum(start) > n:
    start += 1
  else:
    ans += 1
    end += 1

print(ans)

그런데 시간초과가 났다. 로컬에서 천만으로 테스트 해보니 한참 걸리긴 했다.

코드 2 - 통과

n = int(input())

start = 0
end = 1
sum = 1
ans = 0

while start < end and end <= n:
  
  if sum <= n:
    if sum == n:
      ans += 1
    end += 1
    sum += end
    
  elif sum > n:
    start += 1
    sum -= start

print(ans)

합을 저장하는 sum이라는 변수를 생성해서 거기에 end와 start를 빼면서 값을 비교했다.
매번 연산을 했던 1번 코드와 달리 더하기, 빼기만 해서 그런가 이전 코드보다 빨랐던 것 같다.