본문 바로가기

알고리즘90

BOJ 1176 - 섞기 (bit, dp) https://www.acmicpc.net/problem/1176 dp using bitfield중 기본문제. 최대 16명의 학생들의 키와 k값이 주어진다. 학생들을 일렬로 배치했을 때 모든 학생들의 인접한 학생과의 키 차이가 k이초과인 경우의 수를 구해라. f(s,t) : 현재 s, 마지막으로 배치된 인원이 t인 경우의 수 ans = f(0,n) -- (t==n인 경우 아무 인원이나 배치할 수 있다. [0base]) s==(1> a[i]; memset(dp, -1, sizeof(dp)); cout 2020. 1. 22.
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.
Educational codeforces #80 D - Minimax Problem(이분탐색, 비트마스크) https://codeforces.com/contest/1288/problem/D 최대 3e5개의 숫자 배열이 들어온다. 각 배열은 최대 m(m 20 0 1 0 1 1 -> 11 두 배열을 or했을 때 1 1 1 1 1이 되므로 b는 3이상의 최소값을 갖는다. 이번엔 4 이상이면 1, 4미만이면 0으로 바꿔보자 1 0 0 0 0 0 0 0 1 0 OR 연산 후에 1 1 1 1 1이 되지 않으므로 b는 4를 최소값으로 갖지 못한다 여기까지 생각했어도 isPossible(mid) 부분을 구현하는것이 쉽지 않다. 모든 배열에 대해 2중 for문으로 검사하면 n^2으로 시간초과다. 좀더 최적화 해보자 하나의 배열이 갖을 수 있는 비트값은 0 ~ (1 2020. 1. 17.

티스토리툴바