[BOJ](Phython) 1292번 : 쉽게 푸는 문제

www.acmicpc.net/problem/1292

1292번: 쉽게 푸는 문제

a,b = map(int, input().split())
count = 1
while True:
    if count**2 + count >= 2*b:
        break
    else:
        count += 1

ans = []
for i in range(1, count+1):
    ans.extend([i] * i)

print(sum(ans[a-1:b]))

배열에 들어갈 값을 미리 만들기 위해선, B <= 1000이므로 1000!개의 배열을 미리 만들어야 한다. O(n!)은 매우 비효율적이므로 필요한 만큼만 배열을 만들고, 그 배열을 슬라이싱 해야 한다.

 

먼저 1 22 333 4444 순서로 수열을 만든다. 이 개수는 1 2 3 4 ... n n+1 ... 순서다.

시작인 A를 제외하고 끝 B만 봤을때 이 개수는 B보다 같거나 커야 한다.

 

즉, 임의의 n에 대해서 1부터 n개의 수열의 합인 n(n+1) / 2는 B보다 커야 한다.

나누기는 부동소수점 오차의 가능성을 내포 하고 있으므로, 2를 곱하여 계산하면 그 개수는 다음을 만족해야 한다.

이 때 최소가 되는 자연수 n을 구하면 최소한의 배열을 생성할 수 있다.

이를 count = 1하고, while loop을 반복하여 구한다.

 

그 뒤, count = 4였다면 1 2 2 3 3 3 4 4 4 4를 배열에 넣어야 한다.

for loop을 반복하여 i일 때 i를 i개 만큼 가지고 있는 리스트를 ans에 추가한다.

 

시작이 3이고 끝이 7은 슬라이싱에서 2~6만큼이다. 끝 배열은 -1만큼을 슬라이싱 하므로

a:b-1만큼 슬라이싱하고 그 슬라이싱 된 부분만큼 내장함수 sum()을 이용하여 합한 뒤, 그 값을 출력한다.