kthng

boj 7579 : 앱https://www.acmicpc.net/problem/7579 아래와 같이 점화식을 정의한 DP 배열로 문제 해결 가능하다.DP[i] : i의 비용만큼 들였을 때, 확보할 수 있는 최대 메모리 DP[i] = max(DP[i], DP[i - cj] + Memory[j]) 물건의 개수는 최대 100개이고,  0 ≤ c1, ..., cN ≤ 100 이므로, DP 배열은 DP[100001]과 같이 잡으면 되며,전체 (DP배열 크기) * (물건의 개수) 만큼 시간 소요된다.

https://www.acmicpc.net/problem/1126 1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net DP 냄새가 강하게 나는 문제이다. 낮은 탑 높이의 최대값을 f(idx, diff)로 두면. 아래와 같이 점화식을 세울 수 있다. 1. f(-1, 0) = 0 2. f(idx, diff) = max( [1], [2], [3]) 2-1. [1] : f(idx - 1, diff) 2-2. [2] : f(idx - 1, diff + a[idx]) + a[idx] 2-3. [3] : f(..