[백준] (Swift) 17427번 - 약수의 합2

 

🟠 문제

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

17427번: 약수의 합 2

아니 내가 문해력이 진짜 딸리는건가? 문제 이해가 잘 안돼 ㅋㅋㅋㅋ 어쨋든 이것도 문제 세번정도 정독하고 문제 이해 완료하고 풀이시작

🟠 1차원적인 약수구해서 더하는 풀이, 시간초과

🔖 당연히 시간초과 나겠는데?

당연하게 생각한 1차원적 풀이가, N보다 작은 수의 모든 약수를 구해서 합을 구하면 되겠구나 생각했다. 그러고 이렇게 하면 이중for문이 들어가게 되고, sum을 하는 과정에서 또 for문이 들어가는데, 시간초과가 안날까? 하고 범위를 살펴봤는데,, N의 범위는,,,,최대 100만...! 말도안돼, 이중for문이 돌아가서 100만 * 100만이면,,, 어우 상상도 하고 싶지 않은 루프가 생성된다.

import Foundation

private func solution() -> Int {
    let N = Int(readLine()!)!
    var sum = 0

    for i in 1..<N+1 {
        var div = [Int]()
        for j in 1..<i+1 {
            if i == j {
                div.append(i)
                break
            }
            if i % j == 0 {
                div.append(j)
            }
        }
        for d in div {
            sum += d
        }
    }
    return sum
}

print(solution())

위처럼 풀었고, 당연하게 시간초과가 났다. 실제로 xcode 로컬에서 돌려보는데도 10000이 들어가도 엄청난 시간이 소요됐다. ㅋㅋㅋㅋ

자, 그럼 이제 다른 규칙을 찾아보자, for문을 최소화하고, 구해야한다.

🟠 이런 것은 수학적인 측면으로 다가가야해!

바로 떠오르지 않아서 N=10 일때를 전부 적어보았다. 여기서 g(N)을 구하려면, 1은 10개, 2는 5개, 3은 3개, 4는 2개,, 이렇게 나왔다. 규칙을 찾아보면? 10을 1로 나눈 몫을 1에 곱해주고, 10을 2로 나눈 몫을 2에 곱해주고, 10을 3으로 나눈 몫을 3에 곱해주고,, 전부 더해주면 g(N)이 나오는 것이다. 왜 이런 규칙이 나올까?

바로, 아래와 같은 규칙 때문이었다.

1의 배수는 항상 1을 약수로 갖는다
2의 배수는 항상 2를 약수로 갖는다
3의 배수는 항상 3을 약수로 갖는다
4의 배수는 항상 4를 약수로 갖는다
...
10의 배수는 항상 10을 약수로 갖는다.
N의 배수는 항상 N을 약수로 갖는다.

이 규칙 때문이었다. 그래서 1의 배수가 10내부에 10개니까, 1을 10개 갖는 것이고, 2의 배수는 10 내부에 5개니까, 2를 5개 갖는 것이었다. 이 규칙을 사용하면 for문은 한번만 사용이 가능하다. 즉, O(N) 의 시간복잡도로 정답을 구할 수 있다.

🟠 정답

private func solution() -> Int {
    let N = Int(readLine()!)!
    var sum = 0

    for i in 1..<N+1 {
        sum += (N / i) * i
    }

    return sum
}

print(solution())