dh_0e

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

철로 (백준 13334번) 정렬과 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..

N포커 (백준 16565번) 조합론의 포함 배제의 원리를 사용하여 포카드가 나올 경우의 수를 구하는 문제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개의 카드를 뽑을 때 포카드가 나올 경..

휴대폰 자판 (백준 5670번) 개미굴에서 EOF, 소수점 처리가 포함된 변형 문제while (cin >> n)로 EOF 처리, 소수점 처리 잘 해주고 Trie에 size라는 변수, find 함수에 적당한 식을 추가하면 쉽게 해결할 수있음메모리 초과가 났지만 소멸자가 제대로 작동하지 않았음 >> 소멸자 잘 작동하게 수정하니 바로 해결됨 #include#include#includeusing namespace std;char d[100001][81];struct Trie { bool finish; int size; Trie* next[26]; Trie() :finish(false),size(0) { memset(next, 0, sizeof(next)); } ~Trie() { for (int i = 0;..

개미굴 (백준 14725번) 자료구조 Trie를 변형해서 풀 수 있는 문제map로 next에 key값으로 string, value에 Trie의 포인터 값을 저장하게끔 map을 만들어 준 후, input 데이터를 저장해준다.dfs형식의 print 함수를 적절히 만들어 next에 저장된 tree 형식의 데이터를 출력 #include#include#include#include#includeusing namespace std;struct Trie { bool finish; map next; Trie() :finish(false) {}; ~Trie() { for (auto it = next.begin(); it != next.end(); it++) delete(it->second); }; void inser..

전화번호 목록 (백준 5052번) 자료구조 트라이(Trie) 기초 문제로 해시 테이블을 사용해서 풀 수도 있는 문제 Trie를 문제에 맞게 구현해주면 쉽게 풀 수 있다.insert 도중 finish가 true면 일관성 Xinsert가 끝난 후 finish에 true 값을 저장하려는데 number 배열이 비어있지 않으면 일관성 X #include#include#includeusing namespace std;struct Trie { bool finish; Trie* number[10]; Trie() :finish(false) { memset(number, 0, sizeof(number)); } ~Trie() { for (int i = 0; i insert(key + 1); }};int main(){ ..