목록2024/11/14 (1)

후라이

[Gold-4] 2293번 | 동적계획법(DP) | 자바(Java)

https://www.acmicpc.net/problem/2293  해당 문제는 DP를 사용해 주어진 동전의 가치로 해당 금액(k)을 만들 수 있는 경우의 수를 구하는 문제이다.문제 예제와 같이 3가지의 동전과 각각의 가치 1,2,5가 주어졌을 때이 세 가지 종류의 동전으로 10을 만들 수 있는 가지수를 구하는 것이다.  1원 10개1원 8개 + 2원 1개1원 6개 + 2원 2개1원 4개 + 2원 3개1원 2개 + 2원 4개2원 5개1원 5개 + 5원 1개1원 3개 + 2원 2개 + 5원 1개1원 1개 + 2원 3개 + 5원 1개5원 2개쉽게 하나하나 구해보면 위와 같은 총 10가지의 경우의 수가 나오게 될 것이다. 이제 이 문제를 동적계획법(DP)로 풀이해보자.우선, 동전의 가치를 저장할 정수형 배열을..
백준/Gold 2024. 11. 14. 21:01
이전 Prev 1 Next 다음