[백준] 1024번 수열의합

1024번 수열의 합

접근방식

N까지의 합을 구한 값에 K 까지의 합을 구한 값을 빼서 찾는 방식으로 접근하는 것도 생각해보았으나, 시간문제로 힘들 것 같다고 판단하여

N을 만드는 L개의 연속정수에 초점을 맞추었다.
최소 L개이고 최대 100개이므로 시간복잡도를 확 줄일 수 있었다.

L이 홀수고 N % L 이 0이면 N을 만들 수 있고,
L이 짝수이고 N % L == L /2이면 N을 만들 수 있다

시간 복잡도

O(L^2)

Code

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
class IO1024 {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    private val bw = BufferedWriter(OutputStreamWriter(System.out))

    fun getNumList(): List<Int> = br.readLine().split(" ").map { it.toInt() }
    fun flush() = bw.flush()
    fun close() = bw.close()
    fun write(message: String) = bw.write(message)
}

fun main() {
    val io = IO1024()
    val (N, L) = io.getNumList()
    
    val isOdd = { num: Int -> num%2 == 1 }
    
    val sum = { numList: MutableList<Int> -> if (numList.size ==0) 0 else numList.reduce { acc, int -> acc + int } }
    
    val getPlusMinus = { oddFlag: Boolean, num: Int, plusMinus: Int ->
        when (oddFlag) {
            true -> listOf (num-plusMinus, num+plusMinus)
            false -> listOf (num-plusMinus, num + plusMinus + 1)
        }
    }
    
    val ansList = mutableListOf<Int>()
    for (len in L..100) {
        var count = 0
        val oddFlag = isOdd(len)
        val mid = N / len
        var whileFlag = false
        if (oddFlag && N % len == 0) {
            count = 1
            ansList.add(mid)
            whileFlag = true
        } else if (!oddFlag && N % len == len / 2) {
            count = 2
            ansList.addAll(listOf(mid, mid + 1))
            whileFlag = true
        }
        while (count < len && whileFlag) {
            val plusMinus = if (oddFlag) (count + 1) / 2 else count / 2
            if (mid - plusMinus < 0) {
                ansList.clear()
                break
            }
            ansList.addAll( getPlusMinus(oddFlag, mid, plusMinus))
            count += 2
        }
        if (sum(ansList) == N ) {
            break
        } else {
            ansList.clear()
        }
    }
    ansList.sort()
    var message = when {
        ansList.size == 0 -> "-1"
        ansList.size > 100 -> "-1"
        else -> {
            ansList.map { it.toString() }.reduce { acc, str -> "$acc $str" }
        }
    }
    io.write(message.trim())
    io.flush()
    io.close()
}