결국 오고야 마는 것들

유니온 파인드. 이름은 unordered_map을 이용해서 고유 번호를 부여하고 union하는 과정에서 각 집합의 크기를 유지하는 부분을 추가해주면 쉽게 풀린다. #include #include #include #include using namespace std; int parent[200000]; int find(int u){ if(parent[u] < 0) return u; return parent[u] = find(parent[u]); } int merge(int u, int v){ u = find(u); v = find(v); if(u == v) return parent[u]; parent[u] += parent[v]; parent[v] = u; return parent[u]; } int main..

혼내주기 2021. 8. 1. 23:01

문제를 보고 pq로 뽑은 수에 모든 소수를 곱해서 다시 넣어야 겠다는 생각은 했는데, 계속 메모리 초과가 났다. 생각해보니 중복해서 들어가는 수랑 범위를 벗어난 수가 너무 많아보여서 set으로 중복을 제거하고 int 범위 벗어난 수는 다 거르고 넣었는데 메모리 초과가 나왔다. 아마 set에 int 범위 내의 숫자가 너무 많이 들어가서 그런 것 같다. 그래서 set을 없애고 중복을 거르기 위해서 이전에 뽑은 수와 현재 수가 같으면 스킵하는 방식으로 구현하니 메모리 100mb를 사용하고 통과했다. 다른 사람의 코드를 찾아보니 pq에 넣을 때 if(num % arr[i] == 0) break; 한줄만 넣어주면 애초에 중복되는 수를 넣지 않게 되어 메모리와 시간이 압도적으로 절약된다. 뭐랄까 하나만 알고 둘을 ..

혼내주기 2021. 8. 1. 22:59

dp문제긴 한데... 이런 규칙 찾기 문제는 풀어도 영 뿌듯하지가 않다... 최댓값은 홀수인 경우 7 이후에 2마다 1을 추가하고, 짝수인 경우엔 그냥 2마다 1을 추가하면 된다. 최솟값은 숫자별 최소값을 쭉 적어보면 17까지는 예외가 있는데, 18 이후부터는 7 마다 이전 숫자에 8을 더해 만드는 규칙을 찾을 수 있다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int arr[22] = { 0, 0, 1, 7, 4, 2, 6, 8, 10, 18, 22, 20, 28, 68, 88, 108, 188, 200, 208, 288, 688, 888 }; int t; void input() { fastio; c..

혼내주기 2021. 8. 1. 22:56

투 포인터로 구간에서 중복되는 숫자가 k개를 넘어가면 중복된 숫자가 구간에서 제외될 때 까지 왼쪽 포인터를 밀어주면 된다. 지금까지 한칸씩만 밀다가 조건을 만족할 때 까지 포인터를 움직이는 문제는 처음 만나서 좀 헤맸다. 유연한 사고 능력이 부족하다! #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int arr[200000], cnt[100001]; int n, k; void input() { fastio; cin >> n >> k; for(int i = 0; i > arr[i]; } int main() { input(); int ans = 0; for(int e = 0, s = ..

혼내주기 2021. 8. 1. 22:55

처음에 bfs로 방문한 곳을 다시 방문할 수 있으면 -1을 출력하도록 구현했는데 틀렸다. 아무리 생각해도 틀릴 이유가 없는데 틀려서 질문글에서 반례를 찾고 dfs + dp로 바꿔서 풀었다. 반례는 스포 방지를 위해 맨 아래에 적어두었다. 이 문제 또한 실제 코딩테스트 문제였으면 반례를 떠올리지 못했을 것 같다... 경우의 수를 좀 더 엄밀하게 생각하는 능력을 기르고 싶다... #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; bool visited[50][50]; int board[50][50], cache[50][..

혼내주기 2021. 8. 1. 22:55

비트마스크 dp인줄 알았는데 그냥 완전탐색으로 풀 수 있는 문제였다... 이번 문제도 corner case를 잡지 못해서 오래 헤맸다... 멘탈 바사삭... #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; string words[50]; bool check[26]; char must[5] = {'a', 'n', 't', 'c', 'i'}; int n, k, tot = 0, ans = 0; void input() { fastio; for(int i = 0; i > n >> k; for(int i = 0; i < n; ++i) { ci..

혼내주기 2021. 8. 1. 22:54

지이이이ㅣ이인짜 많이 헤맸는데, 결과적으론 처음 짠 코드에서 index 처리를 잘 못해서 지구 한바퀴 돈 셈이다. 우울하다 진짜... #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; string arr[10]; bool check[26]; char alphabet[10]; int match[26]; int n, ans = 0, tot = 0; void input() { fastio; cin >> n; for(int i = 0; i > arr[i]; for(int j = 0; j < arr[i].size(); ++j) { if(check[arr[i][j] - 'A']) contin..

혼내주기 2021. 8. 1. 22:53

#include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int arr[4000][4]; int n; void input() { fastio; cin >> n; for(int i = 0; i > arr[i][j]; } int main() { input(); vector v; v.reserve(n*n); for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) { v.push_back(arr[i][2] + arr[j][3]); } } sort(v.begin(), v.end()); long long ans..

혼내주기 2021. 8. 1. 22:52