문제

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

1
2
3
4
1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
15 = 15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

제한사항

  • n은 10,000 이하의 자연수 입니다.

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(n):
    q = [1]
    answer, i, total = 1, 1, 1
    mid = int((n+1) / 2) # 절반보다 큰 값부터는 값이 없으니 절반까지 반복문 실행
    while i < mid:
        i += 1
        total += i
        q.append(i)
        while total > n:
            total -= q.pop(0)
        if total == n:
            answer += 1
    return answer
  • 원소가 1만 있는 큐(리스트)를 만든다.
  • 주어진 수의 절반까지 반복한다.
  • 차례로 수를 더할 때마다 queue에 수를 추가한다.
    • 더한 값이 원하는 수보다 큰 동안, 큐에서 수를 하나씩 꺼내어 합에서 뺸다.
    • 더한 값이 원하는 수이면 정답 개수를 하나 늘린다.