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

이게 왜 골드지? 했다가 아주그냥 호오온났던 문제!!

 

🟠 문제

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

17425번: 약수의 합

뭐야! 이전에 풀었던 '약수의합2'문제랑 똑같잖아? 근데 그냥 , 입력만 다르게 하면 되는거잖아!!!

 

🟠 시간초과 ^___^

심지어 입력 방식도 잘못알았다. 초반에 입력되는 5를 못보고, 그냥 끝없이 입력이 가능한? 문제인줄 알고 while으로 작성했다.

while let N = Int(readLine()!) {
    print(solution(N))
}

private func solution(_ N: Int) -> Int {
    let N = N ?? 0
    var sum = 0

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

    return sum
}

엥,, 시간초과네? 일단, 초반에 N개를 입력할거라는 T를 입력받았어야했는데, 나는 끝없이 입력이 가능하게 코드르 작성해서 틀린줄 알았다. 근데 ,, 이문제도 아니었다.!!

입력을 제대로 받아도 시간초과였다.

🔖 해결방법을 생각해보자

우선, 예제를보면, T = 5 을 입력받는다. 내 코드를 보면, 만약 5번을 입력받으면, 5번 모두 g(N)을 계산하기 위해서 연산을 반복한다.

예제상황으로 생각해보면
g(1) 을 구하기 위해서 f(1) 구하고 sum인 f(1) 구함
g(2) 를 구하기 위해서 f(1), f(2) 구하고 sum 인 f(1) + f(2) 구함
g(10)을 구하기 위해서 f(1), f(2), f(3), f(4), f(5)....f(10) 구하고, sum 인 f(1)+f(2)+f(3)+...+f(10) 구함
.......
이렇게 반복된다.

쓸데없는 연산이 많아졌다. f(2)를 이전에 구해놨는데, 이를 재사용할 순 없을까? 또, 지금 예제에서만 이정도지, 만약 T = 100000 을 입력받게 되면, 10만번을 연산해줘야한다. 이 연산을 줄이기 위해서는,,, dp 형태로 만들어줘야겠다고 판단했다.

즉, 모든 답을 미리 구해놓고, 마지막에 입력받는 i 에 대해서 dp[i]를 바로 출력할 수 잇게 만들어 놓는 것이다.

[ f(1), f(1)+f(2), f(1)+f(2)+f(3), f(1)+f(2)+f(3)+f(4), ,,,,,,, f(1)+..+f(100000) ]

이렇게 구해보자.

🟠 첫번째 시도

이렇게 코드를 작성했다. 

[ f(1), f(1)+f(2), f(1)+f(2)+f(3), f(1)+f(2)+f(3)+f(4), ,,,,,,, f(1)+..+f(100000) ]

이 형태를 만들기 위해서, div라는 배열을 만들었고, div는 i의 약수의 합을 넣어둔 것이다. 이 메서드를 구하는 것에 대해서도 생각이 조금 필요했는데, 인터넷을 조금 ,, 뒤져봤다 미리 구하기 위해서는 1의 배수에 1씩 더해주고, 2의 배수에는 2를 더해주고, 3의 배수에는 3을 더해주고,,, 이런식으로 100만까지 각 i의 약수의 합을 구해주었다. 그 배열이 바로 div

그리고 sum 배열은 누적합을 구해주었다. 

 

private func solution() {
    let accumulate = accumulateSum()
    let T = Int(readLine()!)!

    for _ in 0..<T {
        let num = Int(readLine()!)!
        print(accumulate[num])
    }
}

private func accumulateSum() -> [Int] {
    var div = Array(repeating: 0, count: 1000000)
    var sum = Array(repeating: 0, count: 1000000)

    for i in 1...1000000 {
        var j = 1
        while i*j < 1000000 {
            div[i*j] += j
            j += 1
        }
    }
    sum[1] = div[1]
    for i in 2..<div.count {
        sum[i] = sum[i-1] + div[i]
    }

    return sum
}

solution()

읭

런타임에러..? 어디 예외를 못잡았나보다.. 도대체 뭘까!

 

🟠 정답 코드

런타임 에러의 문제는 범위였다. 

    var div = Array(repeating: 0, count: 1000000)
    var sum = Array(repeating: 0, count: 1000000)
    
    while i*j < 1000000 { .. }

div 와 sum을 이렇게 설정해주고 while문을 1000000 미만으로 설정해주었다. 이렇게 하게 되니까, N의 최대값인 1000000을 입력할 수 없었다. 그래서 범위를 조절해주면서 런타임에러를 해결했다!

private func solution() {
    let accumulate = accumulateSum()
    let T = Int(readLine()!)!

    for _ in 0..<T {
        let num = Int(readLine()!)!
        print(accumulate[num])
    }
}

private func accumulateSum() -> [Int] {
    var div = Array(repeating: 0, count: 1000001)
    var sum = Array(repeating: 0, count: 1000001)

    for i in 1...1000000 {
        var j = 1
        while i*j <= 1000000 {
            div[i*j] += j
            j += 1
        }
    }
    sum[1] = div[1]
    for i in 2..<div.count {
        sum[i] = sum[i-1] + div[i]
    }

    return sum
}

solution()