본문 바로가기
알고리즘 문제 풀이/동적프로그래밍

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

by 가나무마 2022. 2. 13.
728x90

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

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

 

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

 

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

초보 알고리즘 스터디 / 누구나 참여 가능 :runner:. Contribute to ROUTINE-STUDY/Algorithm development by creating an account on GitHub.

github.com

문의는 댓글 바람.

 

문제 출처 :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])
}

 

728x90
반응형

'알고리즘 문제 풀이 > 동적프로그래밍' 카테고리의 다른 글

백준 - 거스름돈(Kotlin)  (0) 2022.02.23
백준 - 돌 게임(Kotlin)  (0) 2022.02.23
백준 - 이친수(Kotlin)  (0) 2022.02.05
백준 - 계단 오르기  (0) 2022.01.29
백준 - 연속합  (0) 2021.12.23