백준 - 카드 구매하기 2(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/16194

 

[접근 방법]

문제를 못풀고, 다른 사람의 힌트를 보고 풀었다.

그렇다면 나는 왜 풀지 못했을까?

 

1. 시간복잡도

점화식을 유도하는데에는 성공 못했지만, 대충 감은 잡았었다.

예를 들어, 15라면 (1,14), (2,13), (3,12)... (7,8) 

근데 이걸 나는 모든 조합이 필요한 걸로 착각해서 시간복잡도 개념 계산을 잘못했다.

 

[잘못 계산한 시간 복잡도]

실제로는 k=1부터 n까지 k/2번 반복하므로 아래와 같이 될 듯하다.

 

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    // 입력
    val N = readLine().toInt()
    val p = IntArray(N+1)
    val dp = IntArray(N+1)
    readLine().split(" ").map { it.toInt() }.forEachIndexed { index, i ->
        p[index] = i
        dp[index] = p[index]
    }

    for (i in 0 until N) {
        for (j in 0 .. i) {
            dp[i+1] = (dp[j] + p[i-j]).coerceAtMost(dp[i+1])
        }
    }

    println(dp[N-1])
}