[백준/튼튼한기본기] 1292번: 쉽게 푸는 문제

아... 이 문제 때문에 꿈까지 꿨다.

너무나도 컨닝하고 싶었으나 개발새발로라도 스스로 코드를 짜봤다. 따라서 개발새발 주의.

 

[문제]

[내 코드]

A, B = map(int, input().split())

def find_num(n):
    for i in range(n+1):
        thr = (i * (i+1))/2
        n_diff = n - thr
        if n_diff <= 0:
            n_n = i
            return n_n, int(n_diff)
            
def double_sum(n):
    return int(n*(n+1)*((2*n)+1)*1/6)
    

A_n, A_diff = find_num(A)
A_sum = double_sum(A_n) + (A_n*A_diff)

B_n, B_diff = find_num(B)
B_sum = double_sum(B_n) + (B_n*B_diff)

print(B_sum-A_sum+A_n)

..... 이렇게 됐다 (원래 이것보다 훨씬 끔찍했는데 노력한 끝에 괜찮아진 것)

'맞았습니다!!'라도 보고자 하는 마음에.........;;;;;;;;;

 

일단 내가 생각한 흐름은.........

인덱스 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ....

숫자    : 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 5 ....

 

인덱스가 주어졌을 때, 그 인덱스가 해당하는 숫자와, 숫자 군집에서 몇 번째를 차지하는지 알아내야겠다 생각했다

예를 들어 인덱스 7은 숫자가 4이고 4 4 4 4 중에서 첫번째다

 

그래서 n번째 숫자와 군집에서의 번호를 찾는 함수를 먼저 정했다

def find_num(n):
    for i in range(n):
        thr = (i * (i+1))/2
        n_diff = n - thr
        if n_diff <= 0:
            n_n = i
            return n_n, int(n_diff)

군집이 변하는 인덱스(1, 3, 6, 10, ...)가 1, 1+2, 1+2+3, ... 이다.

어쨌든 주어진 인덱스보다 숫자는 작기 마련이므로, 1부터 $\frac{n(n+1)}{2}$를 구하며 인덱스에서 뺐다

뺀 값이 0또는 마이너스가 되는 순간이 숫자 구간이 바뀌는 순간이고, 뺀 값은 구간의 순서에 해당한다

 

예를 들어 인덱스 12가 주어졌으면, 1, 3, 6, 10 까지 빼다가 .. 15 를 빼는 순간 -3이 된다

그 말은 인덱스 12가 해당하는 숫자는 5이고 숫자 5 군집에서 (5-3)번째에 해당된다

 

def double_sum(n):
    return int(n*(n+1)*((2*n)+1)*1/6)

$1^{1}+2^{2}+3^{2}+4^{2}+\cdots$를 구하는 함수다. 즉, $\frac{n(n+1)(2n+1)}{6}$

 

B_n, B_diff = find_num(B)
B_sum = double_sum(B_n) + (B_n*B_diff)

print(B_sum-A_sum+A_n)

 

double_sum와 n_diff(순서)를 써서 그 숫자까지의 합을 구한다

B까지의 합과 A까지의 합을 더한 후 A인덱스의 숫자를 빼면 구간의 합이 된다

 

그런데,

 

 

채점이 되는가 싶다가도 계속 TypeError가 떴다

몇번의 실험 끝에 A나 B가 1이나 2일 때 발생하는 문제라는 걸 깨달았다..

실제로 대입해보니까 안 됐다.. 

 

문제는

여기는 수정되어 있는 상태임

find_num 함수에서 for i in range(n) 으로 했을 때였다

웬만해서는 인덱스값이 숫자보다 커서 range(n) 으로 세팅했는데, 1이나 2일 때는 자기 자신과 같으므로 range가 자기자신까지 돌아야 했다

 

여러모로 자신감이 떨어지고 자괴감이 드는 문제였다...

수열은 다시 공부를 해야겠다

 

 

[개선안]

 

a,b = map(int,input().split())
 
arr = [0]
for i in range(46):
    for j in range(i):
        arr.append(i)

print(sum(arr[a:b+1]))

 

 

.....아

그냥 파이썬으로 수열을 구현하면 됐다.....