Notice
Recent Posts
Recent Comments
Link
목록2293번 (1)
Hello World!
[BOJ] 2293번: 동전 1
문제 링크: 백준/BOJ https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 아주 아주 유명한 dp 문제다. dp[$k_j$] = 가치의 합이 $k_j$원이 되게 하는 경우의 수 즉, dp[5]의 경우 5원을 만들 수 있는 경우의 수를 저장한다. 이 문제를 풀기 위한 점화식은 dp[$k_j$] = dp[$k_j$] + dp[$k_j$ - coin[i]] 이때 주의할 점은 초기값 dp[0]을 설정해줘야 함이다. 그 값을 뭘로 설정해줘야 할지는 조금만 ..
알고리즘/baekjoon
2020. 5. 16. 20:29