백준 1419: 등차수열의 합

주어진 범위의 수들 중 k개의 등차수열의 합으로 표현가능한 수의 수를 구하는 문제다.

초항과 공차가 반드시 자연수이므로 각 k에 맞는 최소한의 수가 존재한다.

 

k = 2)

1 + 2 = 3이므로, left가 3보다 작더라도 3부터 시작한다.

초항 n, 공차 d에서 n + n + d = 2n + d를 만족하는 모든 수가 해당된다.

따라서 3이상의 모든 수가 길이가 2인 등차수열의 합이다. (예: 4 = 1 + 3, 5 = 1 + 4 ...)

 

k = 3)

1 + 2 + 3 = 6이므로, left가 6보다 작더라도 6부터 시작한다.

초항 n, 공차 d에서 n + n + d + n + 2d = 3n + 3d를 만족하는 모든 수가 해당된다.

따라서 6이상의 모든 3의 배수가 길이가 3인 등차수열의 합이다.

 

k = 4)

1 + 2 + 3 + 4 = 10이므로, left가 10보다 작더라도 10부터 시작한다.

초항 n, 공차 d에서 n + n + d + n + 2d + n + 3d = 4n + 6d를 만족하는 모든 수가 해당된다.

수는 10이상의 짝수여야하고, 12는 길이가 4인 등차수열의 합으로 표현할 수 없다.

따라서 10이상의 12가 아닌 모든 짝수가 길이가 4인 등차수열의 합이다.

 

k = 5)

1 + 2 + 3 + 4 + 5 = 15이므로, left가 15보다 작더라도 15부터 시작한다.

초항 n, 공차 d에서 n + n + d + n + 2d + n + 3d + n + 4d = 5n + 10d를 만족하는 모든 수가 해당된다.

따라서 15이상의 모든 5의 배수가 길이가 5인 등차수열의 합이다.

 

문제에서 범위는 최대 10억을 넘지 않으므로, 모두 left(또는 각 k에 맞는 최솟값)부터 right까지 naive한 반복을 돌려도 시간 안에 풀 수 있다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() {
    val writer = BufferedWriter(OutputStreamWriter(System.out))
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val left = reader.readLine().toInt()
    val right = reader.readLine().toInt()
    val count = when (reader.readLine().toInt()) {
        2 -> maxOf(right - maxOf(left, 3) + 1, 0)
        3 -> {
            var count = 0
            val min = maxOf(left, 6)
            for (i in min .. right) {
                if (i % 3 == 0) {
                    count++
                }
            }

            count
        }
        4 -> {
            var count = 0
            val min = maxOf(left, 10)
            for (i in min .. right) {
                if (i and 1 == 0 && i != 12) {
                    count++
                }
            }

            count
        }
        5 -> {
            var count = 0
            val min = maxOf(left, 15)
            for (i in min..right) {
                if (i % 5 == 0) {
                    count++
                }
            }

            count
        }
        else -> throw AssertionError("k range error")
    }

    writer.write("$count\n")
    writer.flush()
    return
}