17427번 - 약수의 합 2

💡 시간 초과를 잘 신경 쓰도록 하자 (1초는 1억번까지 가능)

<시간 초과 발생 코드>

total = 0

for i in range(1,N+1):
    for j in range(1,i+1):
        if i % j == 0:
            total += j

• 매 수마다 약수를 구해 계속 더해주는 식으로 진행하였다.
  
• for 문을 2번 돌렸더니 시간초과 오류가 발생했다..
• 생각해보니 입력이 1 <= N <= 1,000,000 이니 N이 1,000,000일때 최악의 경우 for문을 2번 다 돌아야 한다면 5000만번을 넘어가서 당연히 "시간초과" 발생하였다.

<풀이 코드>

# for문을 1번쓰는 경우
# 각 배수들이 총 몇번 들어가는지 생각하자
for i in range(1,N+1):
    total += i * (N//i)

• 아쉽게도 정말 오랜시간 동안 고민하였지만, 풀이법을 찾지 못해서.. GPT형님에게 조언을 구했다.
• 풀이 해결법은 약수로 생각하는 것이 아닌 "배수"로 생각하는 방식이였다.

풀이 방법
1. 각 숫자 T들은 항상 T의 배수의 약수로 들어간다.
2. 따라서 N이 주어지면 각 숫자들이 N에 몇번 들어가는지를 계산해주면 된다.

N = 10
1의 배수 = 10 // 1 = 10번
2의 배수 = 10 // 2 = 5번
3의 배수 = 10 // 3 = 3번
4의 배수 = 10 // 4 = 2번
5의 배수 = 10 // 5 = 2번
6의 배수 = 10 // 6 = 1번
7의 배수 = 10 // 7 = 1번
8의 배수 = 10 // 8 = 1번
9의 배수 = 10 // 9 = 1번
10의 배수 = 10 // 10 = 1번

따라서, 모든 약수의 합은 i * (N // i)의 합과 동일하다.

정말.. 이런 생각을 못하는게 슬프다.. 눈물..🥲