Kotlin] 백준 17425번 풀이

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

17425번: 약수의 합

 

 

진짜 단순하게 생각하면 그냥 삥 둘러놓고 돌리면서 약수 찾으면 되는거 아닌가 ㅇ0ㅇ ? 싶은데 그러면 진짜 개큰일날수 있음..

왜냐면 범위가 100만 단위이며, 테스트케이스는 10만까지이기 때문이다.. 

테스트케이스가 10만 이상이고, 범위가 100만 이상인걸 일일히 1~100만을 추적할 것인가? 이건 최악의 경우 10만번 돌 동안 1의 약수 + 2의 약수 + ... + 100만의 약수를 전부 구해서 더해야하는 경우를 마주할 수 있다.

 

이게.. 문제에 알고리즘 분류는

 

• 수학
• 정수론
• 누적 합
• 에라토스테네스의 체
• 소수 판정

이렇게 다섯가지로 나와있는데, 가장 간단한건 DP로 푸는게 제일 편하다.. 그리고, 테스트케이스가 최대 10만이므로 메모이제이션으로 100만까지의 약수 합을 전부 다 구해놓은 상태로 구한다.

 

처음에는 에라토스테네스의 체.. 가 있어서.. 소수를 전부 구해놓고 -> 소수를 필터링 한 후에 -> 다시 1부터 돌면서 소수로 나누어 약수의 합을 나누는 공식을 이용하여 값을 구하는 방법을 생각했더니.. 당연히 시간 초과ㅋㅋ ㅜㅜ 당연하지.. 100만번이면 최소 200만번 + 100만 * 소수 배열 탐색 수 라 훨씬 많이 걸린다..

 

그래서 차라리 배열을 돌면서 각 수의 약수의 합을 구한 후에 dp를 통해 약수를 더하는 형식으로 가면 200만번만 돌면 된다.

먼저 2의 약수를 찾는다.

2에도 약수 2를 더하고, 4도 2를 포함하므로 2를 더하고, 6도 ... 이를 2 * 500000 = 1000000 이므로 50만번만 반복하면 된다.

3도 마찬가지로 3을 더하고, 6도 3을 포함으로 3을 더하고, 9도 .. 이를 3 * 333333 = 999999 이므로 333333번만 반복하면 된다.

4도.. 4도 포함 8도 포함 12도 포함.. 4 * 250000 = 100000이므로 25만번만 반복하면 된다.

즉,

배수 숫자 * n(내부 반복문으로 돌아야하는 수) = 100000 =>

n = 100000 / 배수 숫자면 된다.

이를 코드로 나타내보자.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.ceil


fun main(args: Array<String>) {
    question17425()
}

fun question17425() {
    val bufferedReader = BufferedReader(InputStreamReader(System.`in`))
    val bufferedWriter = BufferedWriter(OutputStreamWriter(System.out))

    val mesArray = eratosPrime(1000000)

    val count = bufferedReader.readLine().toInt()

    for(i in 1 .. count) {
        val number = bufferedReader.readLine().toInt()
        bufferedWriter.write("${mesArray[number]}")
        bufferedWriter.write("\n")
    }

    bufferedWriter.flush()
}

// 100만까지 누적합이라.. 생각보다 누적합이 개커져서 정수형으로는 감당불가임. 
// double은 변환과정까지 연산으로 해야하므로, Long을 이용하여 연산과정을 줄임.
fun eratosPrime(size : Int) : Array<Long> {

    val mesArray = Array(size + 1) { 1L }
    val mesAddArray = Array(size + 1) { 1L }

	// 2부터 100만까지 돌면서 배수를 구한다.
    for(i in 2 ..< mesArray.size) {
    	// 해당 배수를 포함한 값을 구한다. 
        // 2일 경우 2 4 6 8 .. 2 * 500000 = 100만 까지 50만번을 반복하여 약수를 더하게 함.
        // 3일 경우 3 6 9 12 .. 3 * 333333 = 999999 까지 333333을 반복하여 약수를 더하게 함.
        for(j in 1..< ceil(mesAddArray.size.toDouble() / i).toInt()) {
            mesArray[i * j] += i.toLong()
        }
    }

	// 약수의 합을 구한다.
    // 먼저 약수의 합을 구한 곳에 현재 약수의 합을 더하면 새로운 약수의 합이 만들어진다(피보나치 수열과 유사).
    // g(2) = g(1) + f(2)
    // g(3) = g(2) + f(3) => (g(1) + f(2)) + f(3)
    // g(4) = g(3) + f(4) => ((g(1) + f(2)) + f(3)) + f(4)
    for(i in 2 ..< mesAddArray.size) {
        mesAddArray[i] = mesAddArray[i - 1] + mesArray[i]
    }

    return mesAddArray

}