[백준] 캡틴 이다솜 (1660)(kotlin)

문제 설명

백준 1660번 문제 링크

입력 및 출력

» 입력

첫째 줄에 입력 N이 들어온다. N은 300,000보다 작거나 같은 자연수이다.

» 출력

첫째 줄에 영식이가 만들 수 있는 사면체 개수의 최솟값을 출력한다.

예제 입출력(테스트케이스)

입력	출력
15	3

문제 풀이1

풀이 참고

import kotlin.math.min

fun main() = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val dp1 = IntArray(128)
    val dp2 = IntArray(128)

    for (i in 1 until 128) {
        dp1[i] = dp1[i - 1] + i
        dp2[i] = dp1[i] + dp2[i - 1]
    }

    val ans = IntArray(N + 1) { Int.MAX_VALUE }
    ans[0] = 0
    ans[1] = 1

    for (n in 2..N) {
        for (i in 1 until 128) {
            if (dp2[i] > n) break
            ans[n] = min(ans[n], ans[n - dp2[i]] + 1)
        }
    }

    println(ans[N])
}

문제 풀이1(시뮬레이션)