냅색3 BOJ 15759 - Talent show (냅색, 이분탐색) https://www.acmicpc.net/problem/15759 어려움 최대 250마리의 소 n마리와 최대 1000의 무게제한W가 주어진다. 각각의 소는 최대 1e6의 무게w와 최대 1e3의 능력t가 주어진다. 소들을 적절히 골라서 무게합이 W이상인 집합 중, 능력합/무게합의 최대값을 x라고 할 때, 1000x의 소수점을 버린 값을 구하라. 고른 소들의 집합을 S라고하면 무게합은 W이상이고 다음을 만족해야 한다. 구해야 할 값은 1000x이므로 이를 y로 치환해서 다시 정리해 보면 다음과 같다. y값 1~250*1000*1000범위에 대해 이분탐색하면 된다. int pos(y) : 능력합/무게합이 y가 가능한지? dp[k] : 무게 합이 k일 때 1000T - yW의 최대값 dp[W] : 무게합이 W.. 2020. 3. 1. BOJ 7579 - 앱 (knapsack[+]) https://www.acmicpc.net/problem/7579 2차원 구조->1차원 구조 설명 한 동전을 단 한번 사용해야 하는지, 여러번 사용할 수 있는지 앱을 끄면 메모리와 비용이 각각 늘어난다. (메모리 m; fill(dp, dp + MAX, 1e9); for (int i = 0; i > b[i]; //메모리 for (int i = 0; i > c[i]; //비용 dp[0] = 0; for (int i = 0; i = 1; j--) if(j-b[i]> m; for (int i = 0; i > b[i]; for (int i = 0; i > .. 2020. 2. 25. CSES PS - Coin combinations (DP) https://cses.fi/problemset/task/1636 점화식 만들기가 쉽지 않다. https://www.youtube.com/watch?v=DJ4a7cmjZY0 영상설명.. 서로 다른 동전의 가치가 최대 100개 주어질때, 이 동전을 이용해서 정확하게 x원을 사용하는 경우의 수를 구해라. (단, 예를들어, 2 2 2 5와 5 2 2 2 는 같은 경우로 친다) 위에서 든 예시와 같은 경우가 생기지 않도록 동전의 순서를 강제해야 한다. f(k, i) = k원을 만드는데 0~i번째 동전을 순서대로 사용해서 만드는 경우의 수. = f(k-a[i], i) + f(k, i-1) ... ->마지막으로 i번째 동전을 사용하거나, 사용하지 않거나 예제로 dp 테이블을 채워보면 다음과 같다. 테이블이 채워지는.. 2020. 1. 16. 이전 1 다음
