dh_0e

비트마스킹을 활용한 dp 문제, 근데 이제 큰 수 % k를 곁들인 .. 시행 착오 vector > dp[][]로 선언을 하여 dp[i][j] = i개의 원소를 합쳤을 때, 마지막 원소에 j번째 원소를 삽입한 pair(first = 지금까지 삽입한 원소들의 비트마스킹, second = k로 나눈 나머지)를 삽입하는 것으로 점화식을 짰다.이 후에 말도 안 되는 메모리 초과를 보여주며 전처리 및 메모리도 줄인 후 진행했는데 여전히 답이 안 보였다. 해결 방안갈아엎었다. 점화식부터 다시 구상하니 dp[i][j] = 지금까지 사용한 원소를 마스킹한 값이 i, 나머지가 j인 수열의 갯수 로 풀 수 있었다.전처리 및 dp에 각각 하나씩 사용한 경우의 수 저장ten_mod에 10^l 들을 k로 나눈 나머지를 모두 구해..

누적 합과 이분 탐색으로 쉽게 풀 수 있는 문제lower_bound, upper_bound 오랜만에 직접 구현해보다가 결국 귀찮아서 라이브러리에 있는 거 썼다.. 풀이 과정누적 합으로 A, B 배열의 부 배열의 합이 될 수 있는 경우의 수를 모두 vector에 저장해준다. (최대 500500 경우의 수)둘 중 하나를 sort 해준다.upper_bound - lower_bound로 target(t - vec_a[i])이 몇 개나 있는 지 구해서 dap에 더해준다.dap은 int 범위를 넘을 수 있으므로 long이나 long long으로 처리해준다.못 찾았을 경우 up, lo 모두 end() 저장소의 위치를 가르키므로 예외처리 안 해줘도 0을 더한다. #include#include#includeusing n..

1~$10^{12}$ 범위인 N과 서로수인 수의 개수를 구하는 문제 깡으로 하면 무조건 시간 초과이므로 오일러 피 함수의 성질을 이용해서 풀 수 있다.  시행 착오에라토스테네스의 체로 소수를 모두 구별하여 N을 소인수분해 한 뒤, 오일러 피 함수의 성질을 이용하여 답을 도출하는 식으로 구상했지만, $10^{12}$ 이하의 가장 큰 소수가 999999999989이므로 당연히 메모리 초과가 나왔다. 풀이 과정사실 2부터 시작해서 N의 값을 나눌 수 있을 때까지 나누면 소수를 따로 구할 필요없이 소수로만 나눌 수 있다.나눌 때마다 오일러 피 함수의 성질을 이용하여 변수를 지정해 곱해놓으면 답을 구할 수 있다. ※ N=99처럼 sqrt(N)보다 N의 약수(11)가 더 큰 경우가 있으므로 이 경우엔 N이 1까지 ..

정렬과 priority queue만 적절히 사용할 줄 알면 쉽게 풀리는 문제  사람들의 집과 사무실의 위치는 바뀌어도 상관 없으므로 first 값이 작도록 설정한 뒤, second 값을 기준으로 오름차순 정렬해줌 (second 값이 같을 경우 first 값 오름차순으로)차례대로 우선순위 큐 top에 있는 사람을 기준으로 범위 안에 들어가는 지 확인O: 우선순위 큐에 i번째 사람 추가, 범위 안에 있는 사람 수가 max인 지 확인X: 범위 안에 들어갈 때까지 top에 있는 사람을 pop해줌 #include#include#includeusing namespace std;pair d[1000001];priority_queue > prique;bool cmp(const pair & a, const pair & ..

조합론의 포함 배제의 원리를 사용하여 포카드가 나올 경우의 수를 구하는 문제dp[N][K] = N장의 카드를 뽑을 때, K개의 포카드 세트가 나올 수 있는 경우의 수를 저장하는 형식으로 1~N까지 차례로 구하며 dp로 풀 수 있을 것 같아서 5시간 동안 점화식을 찾았다... 결론적으로 이 전의 경우의 수는 관계 XN개의 카드를 뽑을 때, K개의 포카드 세트가 나왔다고 고정한 뒤, 나올 수 있는 경우의 수를 구한다.식: $cmp = {_{13}C_K} + {_{(52 - k \times 4)}C_{(N - K \times 4)}}$K를 1~N/4까지 구해준 다음, 포함 배제의 원리에 의해서 홀수번째는 더해주고, 짝수번째는 빼주면 N개의 카드를 뽑을 때 포카드가 나올 경우의 수를 구할 수 있다. ex) N이..