[백준] 9095 (1, 2, 3 더하기)

#1 알고리즘

#1-1

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

상향식 동적 프로그래밍을 구현해 풀었다.

 

이 문제에서 가장 핵심적인 부분은 점화식을 구하는 것이다. 나는 먼저 점화식 calculateCombination(sum) = calculateCombination(sum - 1) + calculateCombination(sum - 2) + calculateCombination(sum - 3) 가 왠지 성립할 것만 같아서 한번 이렇게 제출해봤는데 문제가 풀렸다. 감으로 문제의 정답을 맞춘 것과 별개로, 왜 이 수식이 성립하는지 확인하고 넘어가겠다.

 

#1-2

calculateCombination(sum - 1)의 조합 뒤에+1을 붙이고 calculateCombination(sum - 2)의 조합에 +2 그리고 calculateCombination(sum - 3)의 조합 뒤에 +3을 붙이면 calculateCombination(sum)의 조합을 만들 수 있다. 그보다 더 작은 calculateCombination(sum - 4)의 조합 뒤에는 4를 붙여야 하는데, 이는 문제의 조건인 숫자의 범위 1 ~ 3을 벗어난다. 예를 들어, 5 = 1+4 는 문제의 조건을 만족시키지 않는다.

 

#2 코드 - 코틀린

/* map에 선언과 동시에 초깃값 할당
 * 2 = 1 + 1
 * 2 = 2
 * -> 2의 조합 갯수는 2개
 * 3 = 1 + 1 + 1
 * 3 = 2 + 1
 * 3 = 1 + 2
 * 3 = 3
 * -> 3의 조합 갯수는 4개
 * -> 4의 조합 갯수는 문제에서 7이라고 알려줌
 */
val numberOfSumCombination : HashMap<Int, Int> = hashMapOf(1 to 1, 2 to 2, 3 to 4, 4 to 7)

fun main() { 
    val testCaseCount = readln().toInt()
    for(i : Int in 0..<testCaseCount) {
        val testCase = readln().toInt()
        println(calculateCombination(testCase))
    }
}

fun calculateCombination(sum : Int) : Int {
    if(!numberOfSumCombination.containsKey(sum)) {
        numberOfSumCombination[sum] = calculateCombination(sum - 1) + calculateCombination(sum - 2) + calculateCombination(sum - 3)
    }
    
    return numberOfSumCombination[sum]!!
}