dp 썸네일형 리스트형 [백준 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]가 된.. [백준 1912] 연속합 (Java) https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 접근 방법 다이나믹 프로그래밍 문제였다. 입력받은 수열은 numbers 배열에 담고 dp라는 배열을 하나 더 만들었다. dp에는 i번째까지의 연속합 중 최댓값을 담았다. i번째까지의 연속합 중 최댓값은 이전까지 연속합 중 최댓값(dp[i-1])에 i번째의 수를 더한 값(numbers[i])과 i번째 수를 비교해 큰 값이 해당한다. 이전까지의 합에 현재 수를 더한 것보다 현재 수가 더 크다면 다시 새로 시작해.. [백준 11726] 2*n 타일링 (Java) https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 접근 방법 규칙을 찾아 점화식을 도출해 내야하는 DP 문제였다. 점화식 자체는 찾아내는데 크게 어렵지 않았다. 하나하나 그려가며 합을 비교해보면 dp(n) = dp(n-1) + dp(n-2)의 점화식이 어렵지 않게 도출된다. 문제는 왜 그런가였다. 아래 그림과 같이 비교해보고 쉽게 알 수 있었다. n = 1일 때는 세워진 타일 1개 n = 2일 때는 두 개의 세워진 타일과 눕혀진 타일로 총 2개였다. n = 3일 때부.. 이전 1 다음
