백준 17427번 문제풀이

문제 이해 자체는 어렵지 않았던 문제다.
f(A)는 자연수 A의 약수의 합
g(x)는 x보다 작거나 같은 모든 자연수 y의 f(y)들을 더한 값 = f(y) + f(y-1) + f(y-2) + ... + f(1)

문제 이해는 쉬운 대신, 시간을 어떻게 줄여야하는지 많이 고민했던 문제다. 문제 조건에 시간제한이 0.5초가 있어서 신경써야한다. 처음에 신경쓰지 않고 코드를 작성했을 땐 당연히 시간초과로 실패했다.

n = int(input())
sum = 0

for n in range(1, n+1):
    for i in range(1, n+1):
        if(n%i == 0):
            sum = sum + n//i
print(sum)

처음 작성했던 코드다. 이중 for문이라서 시간초과가 날 게 뻔했지만 일단 생각나는 데로 작성해봤다. n을 i로 나눠서 0으로 떨어지는 값들의 몫만 sum에 더해주는 방식이었다.

0.5초 안에 답을 구하려면 10까지의 약수를 확인해봐야 한다.

10		1 2 5 10		1 -> 10
9		1 3 9			2 -> 5
8		1 2 4 8			3 -> 3
7		1 7				4 -> 2
6		1 2 3 6			5 -> 2
5		1 5				6 -> 1
4		1 2 4			7 -> 1
3		1 3				8 -> 1
2		1 2				9 -> 1
1		1				10 -> 1

10부터 1까지의 약수를 적어봤다. 여기서 한 가지 규칙을 찾을 수 있다.
약수 중에 1의 개수는 10개, 2는 5개, 3은 3개, ... 로 정리된다.

10//1	=10
10//2	=5
10//3	=3
10//4	=2
10//5	=2
10//6	=1
10//7	=1
10//8	=1
10//9	=1
10//10	=1

10을 1부터 10까지 나눈 몫들만 적어봤다. 그랬더니 위에서 찾은 약수들의 개수와 똑같은 모습이 나타나는 것을 확인할 수 있었다.

n = int(input())
sum = 0

for i in range(1, n+1):
    sum = sum + n//i*i
        
print(sum)

이번 문제,, 어려웠다...!

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