[BOJ] 2018: 수들의 합 5 solution

문제 소개

 

2020.02.24 기준,  브론즈 1티어 문제입니다.

문제 분류는 수학입니다.

 

적당한 수학 규칙을 떠올리면 바로 해결할 수 있는 문제입니다.

 

먼저, 문제를 풀 수 있는 아이디어부터 설명하고

코드를 설명하겠습니다.

 

문제 링크

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

2018번: 수들의 합 5

 

아이디어

일단, 우리는 먼저 연속적인 자연수들의 합의 규칙성을 찾을 필요가 있습니다.

 

예를 들어, 4개의 연속되는 자연수의 합을 살펴보겠습니다.

 

1+2+3+4 = 10

2+3+4+5 = 14

3+4+5+6 = 18

...

 

위의 숫자들을 보면 4씩 증가하는게 보입니다.

 

어? 뭔가 길이만큼 증가하는 것 같습니다.

한번 길이가 5일때도 해보겠습니다.

 

1+2+3+4+5 = 15

2+3+4+5+6 = 20

3+4+5+6+7 = 25

...

 

5일때는 결과값이 5씩 증가합니다.

생각해보면 앞에서부터 하나씩 숫자를 더해가면서 결과값이 변하는 것이기 때문에 

당연히 결과값들이 길이만큼 차이가 나게 됩니다.

 

아무튼 이 특징을 이용해봅시다.

 

코드

n = int(input())
s = 0
ans = 0
for i in range(1,n//2+1):
    s+=i
    if (n-s) >= 0 and (n-s)%i ==0:
        ans+=1
print(ans)

python 코드로 간단하게 작성해봤습니다.

위에 설명한 것을 이용해, 우리가 원하는 N을 길이 i의 연속되는 자연수로 만들 수 있느냐를 다음 2가지 조건으로 확인합니다.

1. n-(1~i까지 누적합)이 0보다 크거나 같은지

2. n-(1~i까지 누적합)이 i로 나누었을 때, 나머지가 0인지

 

이 두 조건이 성립하는 i의 개수를 세면 문제는 해결됩니다.

Rmx