[백준] 쉽게 푸는 문제

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

1292번: 쉽게 푸는 문제

 

군수열 문제로 수열 공식을 이용하여 답을 구할 수 있다.

 

i 번째에 해당하는 숫자 찾기(계차수열, 근의 공식)

x = (1 + math.sqrt(1 + 8 * (i - 1))) // 2

 

i 번째에 해당하는 숫자가 처음으로 등장하는 번호 찾기(계차수열)

n = 1 + (x - 1) * x // 2

 

i 번째에 해당하는 숫자까지의 합(n - 1 번째까지의 합 + n 번째부터 i 번째까지의 합)

n - 1 이 x 라면,

1^2 + 2^2 + 3^2 + ... + x^2

+

(i - n + 1) * x

 

import sys, math

def sequenceSum(i):
    if i == 0:
        return i
    else:
        x = int((1 + math.sqrt(1 + 8 * (i - 1))) // 2)
        n = int(1 + ((x - 1) * x // 2))
    
        return int((x - 1) * x * (2 * x - 1) // 6) + (i - n + 1) * x
    
A, B = map(int, sys.stdin.readilne().split())

print(sequenceSum(B) - sequenceSum(A-1))