문제 링크 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 문제 설명 9084, 동전 문제는 주어지는 동전의 단위로 어떤 금액을 만들 수 있는 개수를 구하는 프로그램을 작성하면 된다. 다이나믹 프로그래밍(DP) 유형의 알고리즘으로 이전의 값들을 사용해 문제에서 요구하는 금액을 만들 수 있는 조합의 개수를 구하면 된다. 내 풀이 DP를 사용하야 풀 수 있다는 생각은 하고 있었고, 비슷한 Logic을 떠올리는데는 성공했다. 하지만 ..

문제 링크 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 설명 어떤 한 배낭에 담을 수 있는 무게가 정해져있고 물건들의 무게(w)와 가치(v)가 주어지면 가장 큰 가치를 배낭에 담을 수 있도록 물건을 배낭에 담는 문제이다. 이 문제는 Dynamic Programming(DP)를 사용해서 풀어야하는데 단순한 DP로 풀기는 어렵고 2차 DP 공간을 마련해서 풀어야한다. 내 풀..