[Python] 2737번 연속 합

 

 

 

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

2737번: 연속 합

---

 

22/11/19

 

 

16886번을 풀다가 겸해서 풀게 된 문제로, 전형적인 수학 문제이다.

 

2022.11.22 - [백준 문제 풀이] - [Python] 16886번 나누기 게임

[Python] 16886번 나누기 게임

 

만약 투 포인터나, 슬라이딩 윈도우로 접근한다면 시간 초과가 분명히 날 것이다.

---

 

문제 접근 방식:

 

 

문제를 접근하기에 앞서, $K$개의 연속된 숫자를 더했을 때 보이는 규칙을 찾아야 한다.

 

예를 들어, $K = 2$라고 해보자.

$1+2 = 3$ $2+3 = 5$ $3+4 = 7$ $4+5 = 9$ $...$

규칙이 보이는가?

 

초항이 $3$이고 공차가 $2$인 등차 수열의 형태가 된다.

 

또 다른 예시로, $K = 3$이라고 해보자.

$1+2+3 = 6$ $2+3+4 = 9$ $3+4+5 = 12$ $4+5+6 = 15$ $...$

이번에는 초항이 $6$이고, 공차가 $3$인 등차수열의 형태가 된다.

 

 

이를 일반화 시켜보자.

 

일반화를 한다면, $K$개의 연속된 숫자들을 더한 값은 초항이 $K(K+1)/2$이고 공차가 $K$인 등차수열의 일반항이 될 것이다.

 

 

따라서, 어떠한 숫자 $N$이 만약 $K$개의 연속된 숫자를 더한 값이라면, 위의 일반항에 속해있을 것이다.

 

이 일반항은 최소 $K(K+1)/2$(초항이기 때문)에서 시작을 한다. 또한, 그 일반항은 공차가 $K$라는 사실 또한 알고 있다.

 

따라서, 어떠한 숫자 $N$에서 $K(K+1)/2$을 뺀 후 그 값이 $K$값으로 나눠진다면, 우리는 $N$이 그 등차수열의 일반항에 속해있다고 할 수 있다.

 

 

이를 참고하여 우리는 $K = 2$에서부터 점점 위로 올라가며 어떠한 숫자 $N$이 정말 $K$개의 연속된 숫자들을 더한 값이 되는지 확인하면 된다.

 

이때, 확인해야 되는 $K$의 범위가 어디까지인지는 다음과 같다.

 

$K$개의 연속된 숫자를 더한 값의 초항이 $K(K+1)/2$이기 때문에, 이 초항은 우리가 확인하는 숫자 $N$보다 커서는 안된다.

 

따라서, $K(K+1)/2 \leq N$   $\rightarrow$   $K(K+1) \leq 2N$   $\rightarrow$   $K^2 + K + 1/4 \leq 2N + 1/4$   $\rightarrow$   $(K + 1/2)^2 \leq 2N + 1/4$   $\rightarrow$   $K+ 1/2 \leq \sqrt{2N + 1/4}$   $\rightarrow$   $K \leq \sqrt{2N + 1/4} - 1/2$   $\rightarrow$   $K <  \left \lfloor \sqrt{2N + 1/4} - 1/2 \right \rfloor$ 가 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2737번 연속 합
# 수학, 정수론, 브루트포스
from math import *
T = int(input())
for _ in range(T):
    N = int(input())
    total = 0
    for i in range(2, floor(sqrt(2*N+1/4)-1/2)+1):
        if (N - i*(i+1)//2)%i == 0:
            total += 1
    print(total)