[백준 9095번] [Kotlin] 1, 2, 3 더하기

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

난이도 : 실버 3
태그 : 다이나믹 프로그래밍

 

 

설명

정수 4를

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

으로 나타내는... 프로그램을 짜고 있었는데 뭔가 이상했습니다.

이 문제, 뭔가 실버3 같지가 않았습니다.

 

뭔가 쌔한 느낌을 받은 저는,

어... 이거 생각해보니 굳이 1, 2, 3으로 나타낼  필요까진 없네? 라는 것을 뒤늦게야 깨달았고,

아 이거 점화식이구나! 라는 생각이 마침내 떠올랐습니다.

 

그 즉시 각 항들을 구해보며 규칙성을 찾기 시작했습니다.

 

a[1] = 1

1

 

a[2] = 2

1+1

2

 

a[3] = 4

1+1+1

2+1

1+2

3

 

a[4] = 7

1+1+1+1

1+1+2

1+2+1

2+1+1

2+2

1+3

3+1

 

a[5] = 13

1+1+1+1+1

1+1+1+2

1+1+2+1

1+2+1+1

2+1+1+1

1+2+2

2+1+2

2+2+1

1+1+3

1+3+1

3+1+1

2+3

3+2

 

줄줄이 구해보니, a[i] = a[i-1] + a[i-2] + a[i-3] (a>3) 이라는 규칙을 찾을 수 있었습니다.

점화식도 구해졌겠다, 이제 점화식 그대로 코드로 옮기기만 하면 끝이였습니다.

 

 

소스코드

val dp = Array(11) { -1 }

 

다이나믹 프로그래밍에서 쓸 dp 배열을 하나 선언합니다.

 

fun funDP(n: Int): Int {
    return if (dp[n] == -1) {
        dp[n] = funDP(n - 1) + funDP(n - 2) + funDP(n - 3)
        dp[n]
    } else {
        dp[n]
    }
}

위에서 구한 점화식을 그대로 재귀함수로 구현하였습니다.

배열의 값이 이미 구한 상태라면 해당 값을 반환하고,

구하지 않은 값이라면 ( = -1) 재귀적으로 호출하여 해당 값을 구합니다.

 

fun main() {
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4

    for (i in 0 until readLine()!!.toInt()) {
        println(funDP(readLine()!!.toInt()))
    }
}

이제 메인 함수에서 해당 함수를 호출해주면 됩니다.

해당 점화식은 a[i]에서 i>3일때 유효하므로, 1,2,3 인덱스는 직접 지정해주었습니다.

 

 

후기

굳이 1,2,3 덧셈 형태를 출력하는게 아닌데도,

1,2,3 덧셈 형태를 구하려 애를 쓰느냐고 꽤 삽질을 했던 문제였습니다.