문제 출처 : https://www.acmicpc.net/problem/2156 문제 해결에 필요한 알고리즘 : DP ( Dynamic Programming ) 해설마시는 순서는 상관이 없기에 포도주를 1번부터 순서대로 마신다고 가정함. dp와 ar의 인덱스는 0번부터 시작함. i = 0 일 때dp[i][2] = dp[i][0] = 0dp[i][1] = ar[i] i > 0 일 때dp[i][0] = max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2])dp[i][1] = dp[i - 1][0] + ar[i]dp[i][2] = dp[i - 1][1] + ar[i] dp[선택한 포도주의 번호][연속으로 마신 포도주의 개수] = 마시는 포도주 양의 최댓값ar[포도주의 번호] = 포도..
문제 출처 : https://www.acmicpc.net/problem/9084 문제 해결에 필요한 알고리즘 : DP ( Dynamic Programming ) 해설 이 문제는 간단한 동적계획법으로 해결이 된다. 아이디어는 간단하다. 동전을 순차적으로 고를 때 각 동전마다 몇개씩 고를지 계산하면 된다. N개의 동전종류가 남았을 때 M원을 만들 수 있는 경우의 수를 DP[N][M] 이라고 가정하고 부분문제로 나누면 동전 종류가 N - 1개가 남았고 현재 동전을 1개 선택한 경우 동전 종류가 N - 1개가 남았고 현재 동전을 2개 선택한 경우 ... 모든 경우의수의 합이 정답이 된다. 따라서 위의 점화식을 얻게 된다. 시간복잡도 DP테이블을 다 채우는데는 N * M의 시간복잡도를 가진다. 또 find함수 내..
문제 출처 : https://www.acmicpc.net/problem/16194 문제 해결에 필요한 알고리즘 : DP ( Dynamic Programming ) 해설 이 문제는 정해진 갯수의 카드를 최소값으로 사는 문제이다. 1 ~ N 개의 카드세트가 있을 때, N개의 카드를 가장 싸게 구하는 문제이다. 이 문제는 간단한 부분 문제로 나눌 수 있다. N개의 카드를 살 때 가장 싸게 사는 방법은 선택한 카드의 갯수만큼 가장 싼 값에 산다고 가정했을 때, 이 중 하나일 것이다. 카드 N개를 산다. 카드 N - 1개와 1개를 산다. 카드 N - 2개와 2개를 산다. ... N - 1개를 산다고 가정하면 N - 1개를 최솟값으로 살 수 있는 경우를 탐색해야한다. 이 때 (N - 1) - 1개와 1개를 산다고 ..