Kotlin] 백준 17427번 풀이

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

17427번: 약수의 합 2

 

 

이 문제는 하단 문제와 유사하지만 전혀 다른 문제다.

https://itstudy-mary.tistory.com/587

Kotlin] 백준 17425번 풀이

 

위의 문제는 1초에 100만을 돌아 그 중에 케이스를 뽑아내는거지만, 이 문제는 n개의 약수의 합을 0.5초(ㅋㅋ) 만에 뽑아내야한다는게 문제이다. 그래서 이 문제는 단순히 돌아서 뽑아내는게 아니라 약수의 규칙을 알아야한다.

 

규칙을 알기 위해 1~9까지의 수가 어느 숫자를 약수로 가지는지 살펴보자.

 

	1	2	3	4	5	6	7	8	9
1	o	o	o	o	o	o	o	o	o
2		o		o		o		o
3			o			o			o
4				o				o
5					o
6						o
7							o
8								o
9									o

 

1은 9개

2는 4개

3은 3개

4는 2개..

 

여기서 규칙성이 보인다.

바로 9/i 라는 점이다. 9/1 = 9, 9/2 = 4 , 9/3 = 3, 9/4 = 2, 9/5 = 1 이고, 이 규칙은 정확히 들어맞는다.

따라서, 약수의 합은 9*1 + 4*2 + 3*3 + 2*4 + ... = (9/1)*1 + (9/2)*2 + (9/3)*3 + (9/4)*4 + .. = (n/i) * i의 식을 가진다.

이를 코드로 표현하면

 

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

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

fun question17427() {

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

    val number = bufferedReader.readLine().toInt()
    var sum = 0L
    for(i in 1 .. number) {
        sum += (number / i) * i
    }

    println(sum)

}