다이나믹 프로그래밍 썸네일형 리스트형 [백준 11057] 오르막 수 (Java) https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net 접근 방법 전형적인 DP문제라고 하는데 역시나 아직 많이 부족함을 느낀다. 2차원배열을 사용한다. dp[N][0~9]로 수의 길이가 N번일 때, 마지막 자리수가 0 ~ 9 경우의 개수를 각각 담는다. 우선 dp[1][0~9]는 모두 1로 따로 설정을 해둔다.. [백준 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 다음
