DP19 CSES PS - Elevator Rides (bit, dp) https://cses.fi/problemset/task/1653/ 쉬운 설명의 어려운 문제 bit쓰는 dp중엔 기본문제인 듯 하다. https://suuntree.tistory.com/124?category=797985 비슷한 유형의 더 어려운 문제 최대 20명의 사람들의 몸무게가 주어질 때, 최대 하중이 x인 엘레베이터에 사람을 채워 보내는 최소 운행 횟수를 구해라. (몸무게 2020. 1. 22. Educational codeforces 67 div2 E - tree painting (dfs, dp, rerooting, tree) https://codeforces.com/contest/1187/problem/E 항상 궁금했던 그래프+dp 유형. editorial피셜로 기본문제라고 한다. https://suuntree.tistory.com/126?category=805933 트리에서 모든정점 사이즈 선형시간에 구하는 법 트리가 주어진다. 임의의 정점 하나를 선택한다. 그 정점을 루트로 취급할 때 그 서브트리의 모든 정점들의 size합을 구한다. 그 값 중 최대를 구해라. dp[u] : u를 트리의 루트로 봤을 때 모든 정점의 사이즈 합 위 예시와 같이 루트를 바꿨을 때 dp값이 바뀔 여지가 있다. dp값이 바뀐다면 참조투명하지 않다는 것인데, rerooting 테크닉을 사용하여 이를 극복하는 것에 유념하여 보면 된다. 일단 직관적으.. 2020. 1. 21. 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. BOJ 1086 - 박성원 (dp, bit set) https://www.acmicpc.net/problem/1086 비트셋을 이용한 어려운 dp 수가 최대 15개 주어질 때, 이 수를 모두 사용한 순열을 순서대로 이어붙인 숫자 중 k(최대100)로 나눠떨어지는 것의 개수를 이용해서 확률을 구하라. dp[i][j] : i(집합) 골랐을 때 나머지가 j인 것의 수. 초기값은 0으로 한다. (단, dp[0][0] = 1) 최종적으로 dp[(1> k; for (int i = 0; i < n; i++) { for (int j = 0; j < len[i]; j++) { a[i] = a[i] * 10 + (num[i][j] - '0'); a[i] %= k; } } vector ten(51); //10의 i승의 k 모듈러값 ten[0] = 1; for (int i =.. 2020. 1. 5. 이전 1 2 3 4 5 다음
