20200806 // 삼성 SW Expert 아카데미 문제 // 5213

삼성 SW Expert 아카데미 5213번 "진수의 홀수 약수" 문제입니다.

lst = [0] * 1000002
for i in range(1, 1000001, 2):
    for j in range(i, 1000001, i):
        lst[j] += i
        
for i in range(1, 1000001):
    lst[i+1] += lst[i]

TC = int(input())   
ans = []
for tc in range(1, TC + 1):
    k = "#"+str(tc)
    L, R = map(int, input().split())
    k += " " + str(lst[R] - lst[L-1])
    ans.append(k)
for e in ans:
    print(e)

 

이 문제는 못 푼 문제다. 5시간 고민하고 답을 봤는데 어이가 없어서 포스팅하는 문제다.

 

L부터 R까지 홀수인 약수의 합을 구하는 문제인데 에라스토테네스의 체를 써서 최대한 연산을 줄이고 시간을 줄이는

 

방식을 써봤는데 시간초과가 나길래 어떻게 푸나 봤는데 그냥 간단한 문제였다. for문을 돌려서 홀수를 인덱스의 배수에

 

더해서 각각 인덱스에 인덱스에 맞는 홀수 약수의 합을 저장하고 그 값을 참조하는 방식이다. 확실이 약수를 구하는

 

연산을 안하다 보니 시간이 확실히 준다. 이번 문제로 문제를 다른 관점으로 보는 것을 다시 배웠다.