<백준> 동전 1(Gold 5)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/baekjoon%20%EB%AC%B8%EC%A0%9C%EC%A7%91/%EB%8F%99%EC%A0%84%201

[백준]

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

제출결과

 

익숙한 문제라고 생각하고 고민하는데도 안 풀리는 문제였다.

뭔가 어제 오늘 다 머리가 굳어있는 느낌이다.

어서 회복해야할텐데... 밥을 더 많이 먹어야겠다!!

 

이 문제는 보자마자 DP 문제겠거니 했다.

약간 거스름돈 문제가 생각나기도 했다.

그런데 접근이 안 되더라

1차원 배열을 써야할지, 2차원 배열을 써야할지 감이 잘 안 왔다.

내가 최대로 진행한 것은 각 동전을 리스트에 저장해놓은 것이다.

이렇게 해놔야지 각각 동전을 썼을 때에 대한 처리가 가능할 것 같았기 때문이다.

 

그래서 도움을 받았다.

도움을 받고 보니 DP 문제는 역시 손으로 직접 써봐야한다는 깨달음을 또다시 얻었다.

직접 손으로 해봤으면 이 점화식을 찾을 수 있었을 텐데 그냥 멍하니 모니터만 보면서 풀려고 하니 이게 쉽게 생각날리가 있나...

동전을 하나씩 추가하면서 1차원 DP 배열을 업데이트하여 최종적으로 k원의 가치를 가지게 하는 흐름이었다.

그 때마다 현재 사용한 동전의 크기가 업데이트를 시켜줬다.

 

이 문제는 잊어먹을 때 쯤에 다시 풀어봐야겠다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.util.StringTokenizer

var tokenList = mutableListOf<Int>()
var dp = Array(10001) { 0 }
fun main() = with(System.`in`.bufferedReader()) {
    val st = StringTokenizer(readln())
    val n = st.nextToken().toInt()
    val k = st.nextToken().toInt()

    for (i in 0 until n) {
        tokenList.add(readln().toInt())
    }

    solve(n, k)

    println(dp[k])
}

fun solve(case: Int, value: Int) {
    dp[0] = 1
    for (i in 0 until case) {
        for (j in tokenList[i]..value) {
            dp[j] += dp[j - tokenList[i]]
        }
    }
}

 

<참고>

https://velog.io/@jxlhe46/%EB%B0%B1%EC%A4%80-2293%EB%B2%88.-%EB%8F%99%EC%A0%84-1-bfi120m5