Swift) 백준 17425번 (약수의 합)

요구능력 : 시간을 고려하여 TestCase문제를 풀 수 있느냐.. 

 

문제설명 : 

이 문제는 브루트포스로 접근하면 바로 시간초과가난다.. 필자가 그랬다.

TestCase문제는 브루트포스로 낚시를 하기때문에 답을 미리 만들어 놓은다음 테스트케이스에 따른 결과를 도출하는게 좋다.

아래 코드를 보면 dp[i*j] += i 가 적혀있다.

i는 배수를 의미한다.

i가 2라고 가정해보면 2의배수에 전부 2를 더하는것이다.

j는 1부터 1씩 더해진다.

dp[2 * 1] += 2

dp[2 * 2] += 2

dp[2 * 3] += 2

.

.

.

왜 저렇게 구하는거지? 라고 하면 그냥 이게 약수 구하는데는 제일효율적  같은 연산을 여러번 반복 하지않고 한번에 하기 때문이다.

우리가 구하고자 하는수는 100만까지라서 dp[1000000] 까지만 while문을 돌려준다.

그리고 누적 약수의 합을 저장하는것을 보여주면 아래와 같다.

s[j] = s[j - 1] + dp[j]

 

j = 2

s[2] = s[1] + dp[2]

s[3] = s[2] + dp[3]

.

.

.

앞에 누적되어있는 값 + 구하고자하는 자리의 dp값을 하여 값을 누적시킨다.

 

후기 : 수학문제는 대체적으로 시간초과가 많이 나는것같다.. 이 문제도 시간초과가나서 도저히 방법이 생각나지 않아 구글링해봤고 이해는 완료했지만.. 비슷한문제가 있다면 풀어보고싶다 😂

앞으로 TestCase문제가 나오고 시간이 모자르다면 답을 미리 만들어놓고 도출해야겠다.

 

var dp = Array(repeating: 1, count: 1000001) //각자 약수의 합을 저장
var s = Array(repeating: 1, count: 1000001) //누적 약수의 합을 저장
for i in 2...1000000 {
    var j = 1
    while i*j <= 1000000 {
        dp[i*j] += i
        j += 1
    }
}

for j in 2...1000000 {
    s[j] = s[j - 1] + dp[j]
}

let T = Int(readLine()!)!
for _ in 1...T {
    let n = Int(readLine()!)!
    print("\(s[n])")
}