[백준] 17626 (Four Squares)

#1 알고리즘

#1-1 17626번 문제의 함정

n이 18인 경우를 예로 든다. 경우 a보다 b의 '제곱수 합의 최소 갯수'가 더 작다. 즉, 무작정 제곱수의 밑을 큰 수로 둔다고 그게 반드시 정답인 것은 아니다.
 

#1-2 점화식

x의 제곱수 합의 최소 갯수를 반환하는 함수 f(x)를 가정한다. 이러면, a와 b 각각의 4²와 3²를 f(x)에 넣으면 f(4²) = 1이고 f(3²) = 1이다. 즉, 모든 빨간 부분은 f(x)에 넣으면 1로 그 값이 같다. 여기에서 f(x) = 1 + f(y)라는 식을 도출할 수 있다. y값은 a의 경우 18 - 4², b의 경우 18 - 3², c의 경우 18 - 2²다. 이를 일반화하면 f(x) = 1 + f(x - i²)다. i의 범위는 1 ~ (x의 제곱근을 넘지 않는 정수의 최댓값)인 정수다. 결론적으로, f(x)는 재귀 함수다.

 

#1-3 동적 프로그래밍

동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근

#1-2에서 도출한 공식 f(x) = 1 + f(x - i²)에서 동적 프로그래밍을 사용할 수 있음이 보인다. 먼저, 큰 문제의 해에 작은 문제의 해가 포함되어 있다. 그리고 방금 도출한 공식은 재귀 호출 그 자체다. 마지막으로 재귀 호출의 과정에서 아주 많은 중복이 발생한다. 따라서 동적 프로그래밍을 적용할 수 있다. 나는 이 문제를 상향식 동적 프로그래밍을 구현해 풀었다.
 

#1-4 문제 풀이 개요

동적 프로그래밍에서의 '작은 문제'를 저장하기 위한 배열 dp을 선언하고, f(x)의 해를 dp[x]에 저장해나간다.
 

#1-5 동적 프로그래밍에서 '작은 문제'의 해 저장

#1-4에서 f(x)의 값을 dp[x]에 대입해 나갈 것이므로, #1-2을 위과 같이 수정할 수 있다.
 

#1-6 재귀 함수 f(x)의 내용

f(x) 함수의 내용은 위와 같다. f(x)가 뱉는 값(= dp에 저장된 원소의 초깃값이 아닌 값)의 범위는 1 ~ 4이므로, min의 초깃값인 5보다는 반드시 작을 것이다.
 

#2 여담

동적 프로그래밍 문제인줄 모르고 하루 종일을 날렸다. 반대로, 동적 프로그래밍 기법으로 접근하니 굉장히 수월했다. 우리나라만 그런 것인지는 몰라도, 더 큰 문제를 풀기 위한 더 작은 문제의 해를 저장하는 객체를 dp(Dynamic Programming)라고 명명하는 것 같다. 그래서 나도 대세(?)에 따랐다. 물론, dp라는 이름이 나쁜 것은 아니라고 생각한다. 객체의 목적이 분명하게 보이기 때문이다. 아래 있는 코드에서 배열 dp에 내가 붙였던 원래 이름은 leastSquareCounts였다.
 

#3 코드 - 코틀린

import kotlin.math.floor
import kotlin.math.sqrt

val dp = Array(50001) {0} // dp[0]은 사용하지 않음

fun main() {
    // 바텀업 방식의 동적 프로그래밍으로 배열 초기화
    for(i: Int in 1..50000) {
        dp[i] = calculateDp(i)
    }

    // 출력
    val n = readln().toInt()
    println(dp[n])
}

fun calculateDp(n: Int): Int {
    if(isIntegerSquareLoot(n)) {
        return 1
    }

    var min = 5
    for(i: Int in 1..flooredSquareLoot(n)) {
        /* 점화식 dp[x] = 1 + dp[x - i제곱]이 성립함을 이용한다.
         * (n-i*i < n)이면서 상향식 접근(Bottom-up approach)이므로,
         * 값이 아직 동적 할당되지 않은 dp의 원소가 참조될 일은 없다.
         */
        min = minOf(min, 1 + dp[n-i*i]) // 최솟값 갱신
    }
    return min
}

fun flooredSquareLoot(sum: Int): Int {
    return floor(sqrt(sum.toDouble())).toInt()
}

fun isIntegerSquareLoot(number: Int): Boolean {
    return flooredSquareLoot(number) * flooredSquareLoot(number) == number
}

 

#4 실패한 코드 - 스택 오버플로우 런타임 에러 - 코틀린

import kotlin.math.floor
import kotlin.math.sqrt

val dp = Array(50001) {0}

fun main() {
    val n = readln().toInt()
    println(calculateDp(n))
}

fun calculateDp(n: Int): Int {
    if(dp[n] != 0) { // 캐싱된 데이터가 존재하면 return
        return dp[n]
    }

    if(isIntegerSquareLoot(n)) {
        dp[n] = 1 // 캐싱
        return dp[n]
    }

    var min = 5
    for(i: Int in 1..flooredSquareLoot(n)) {
        /* 점화식 dp[x] = 1 + dp[x - i제곱]이 성립함을 이용한다.
         * (n-i*i < n)이면서 상향식 접근(Bottom-up approach)이므로,
         * 값이 아직 동적 할당되지 않은 dp의 원소가 참조될 일은 없다.
         */
        min = minOf(min, 1 + calculateDp(n-i*i)) // 최솟값 갱신
    }
    dp[n] = min // 캐싱
    return dp[n]
}

fun flooredSquareLoot(sum: Int): Int {
    return floor(sqrt(sum.toDouble())).toInt()
}

fun isIntegerSquareLoot(number: Int): Boolean {
    return flooredSquareLoot(number) * flooredSquareLoot(number) == number
}

하향식 동적 프로그래밍으로도 이론상 풀 수는 있다. 하지만, 재귀호출이 계속 반복되면 언젠간 상한선에 닿게 된다. 그리고 그 때 스택 오버플로우 에러가 발생한다. 내 노트북으로는 재귀호출이 평균 1만번 정도 반복되면, 스택 오버플로우 에러가 났다. 물론, 스택 오버플로우 에러가 날 정도로 재귀호출이 많지 않은 경우에는 정상적으로 답을 내뱉는다.