dynamic programing 썸네일형 리스트형 [백준 11052] 카드 구매하기 (Java) https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 접근 방식 이전에 풀어봤던 문제(아마도 백준 2293 동전 문제인 듯하다)와 유사한 부분이 있어서 크게 어렵지 않게 풀 수 있었던 DP문제였다. 문제에서 주어진 예시를 가지고 설명을 하고자 한다. 민규가 구매하려고 하는 카드의 개수 N = 4 P1 = 1, P2 = 5, P3 = 6, P4 = 7 n개의 카드를 갖기 위해 지불하는 금액의 최댓값을 dp[n]이라고 하자. 만약 민규가 카드 1개를 갖는다고 .. [백준 2156] 포도주 시식 (Java) https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 접근 방법 다이나믹 프로그래밍 문제로 이전에 풀었던 백준2579 계단 오르기와 유사해서 비슷하게 접근하였다. DP[n]이 n번째 포도.. [백준 2293] 동전 1 (Java) https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 접근 방법 DP문제로 우선 점화식을 도출해야했다. 동전의 가치가 a, b, c라고 할 때 합이 k가 되도록 하는 동전의 경우의 수는 (k-a)원이 되는 경우에 a를 더한 경우, (k-b)원이 되는 경우에 b를 더한 경우, (k-c)원이 되는 경우에 c를 더한 경우로 총 3가지 경우가 있을 수 있다. 이를 점화식으로 도출하면 DP[k] = DP[k - a] + DP[k -b] + DP[k -c]가 된.. 이전 1 다음
