문제https://www.acmicpc.net/problem/7576시간 제한메모리 제한solved.ac 티어1초256MB골드 5풀이 너무나도 진하게 나는 BFS의 냄새가 아닐수 없다. BFS에 사용할 큐에 토마토의 좌표를 미리 입력한 다음, 전형적인 BFS를 하면 될 것이다.코드#include using namespace std;int m, n;vector> tomato;queue> q;void input() { cin >> m >> n; tomato.resize(n, vector(m)); for(int r = 0; r > tomato[r][c]; if (tomato[r][c] == 1) { q.emplace(0, r, c); tomato[r][c] = -1; } } }}void b..
문제https://www.acmicpc.net/problem/1197시간 제한메모리 제한solved.ac 티어1초128MB골드 4풀이 문제 이름이 정답인 문제다. 최소 스패닝 트리(Minimum Spanning Tree, MST), 최소 신장 트리라고 하는 이 문제는 임의의 그래프가 주어졌을 때, 모든 정점을 최소한의 비용으로 모두 연결하는 알고리즘이다. MST를 구하는 알고리즘은 세가지가 있다. 프림, 솔린, 크루스칼 알고리즘이 있는데, 나는 유니온파인드 자료구조도 같이 공부할 겸 크루스칼을 공부한 상태이다. 크루스칼 알고리즘은 나중에 언젠가 정리하겠지만, 간단하게 설명하면 모든 정점을 유니온파인드 자료구조에서 루트노드인 상태, 그러니까 미연결상태로 둔 뒤, 간선의 가중치를 오름차순으로 정렬한다. 간선..
문제https://www.acmicpc.net/problem/10854시간 제한메모리 제한solved.ac 티어1초256vMB플래티넘 1풀이 밀린 문제 정리하기. 폴라드-로 남은 문제이다. 말은 번지르르한데, 결국 n의 인수의 개수를 세는 문제이다. n이 크기 때문에 폴라드로 인수분해를 통해 찾아주고, 약수의 개수를 세면 된다.코드#includeusing namespace std;using ll = int64_t;using ull = uint64_t;struct Random { mt19937 rd; Random(int seed = (unsigned)chrono::steady_clock::now().time_since_epoch().count()) : rd(seed) {} template T GetInt..
문제https://www.acmicpc.net/problem/7501시간 제한메모리 제한solved.ac 티어1초128MB다이아몬드 5풀이 일단 영어 지문을 읽으면 토악질이 나오는 나지만, 그래도 해석은 가능한 수준의 영어라 읽어보았다. 이러니 저러니하지만, 정리하면 구간 [A, B]에서 다음을 만족하는 정수를 K를 구하는 문제이다.K는 홀수이다.(K-1)! ł K^2. 즉 (K-1)!은 K^2로 나누어 떨어지지 않는다.정수론에서 제일 특별한 수는 항상 소수이다. 이 문제에서도 소수와 소수가 아닌 경우를 생각해보자. K가 소수라면, (K-1)!은 절대로 K^2로 나누어 떨어지지 않는다. 증명도 간단하다. 귀류법으로 생각해서 (K-1)!이 K^2으로 나누어 떨어진다고 해보자. 이는 (K-1)!의 소인..
문제https://www.acmicpc.net/problem/4149시간 제한메모리 제한solved.ac 티어1초128MB플래티넘 1풀이 밀린 문제 정리하기. 오일러 피함수 정리하다가 갑자기 폴라드-로 알고리즘으로 넘어간 나. 그래서 이번엔 폴라드-로 알고리즘이다. 저번 문제에서 설명했지만, 폴라드-로 알고리즘을 사용하여 O(N^1/4)의 시간복잡도로 풀어낼 수 있다. 해당 문제에 적용하면 최대 2^15.5번의 탐색을 거친다 5만번도 안된다. 폴라드-로 문제에 대한 설명은 다음을 참조하자.https://codejin.tistory.com/308 코드#include #define ALL(X) X.begin(), X.end()#define endl '\n'using namespace std;using ll ..
문제https://www.acmicpc.net/problem/13926시간 제한메모리 제한solved.ac 티어2초512MB다이아몬드 5풀이 밀린 문제 정리하기. 오일러 피함수 문제이다. 그런데 밀러라빈 소수 판별법과 폴라드-로 알고리즘을 섞은... 괴랄한 알고리즘의 문제이다. 저번 GCD(n,k) = 1와 설명은 같은 문제이다. (https://codejin.tistory.com/306) 백준 11689번 C++ 풀이문제https://www.acmicpc.net/problem/11689시간 제한메모리 제한solved.ac 티어1초256MB골드 1풀이 밀린 문제 정리하기, 오일러 피함수 문제는 계속된다. 오일러 피함수에 대해 계속 정리중이기 때문에, 해당codejin.tistory.com 저번 문제의 경..
문제https://www.acmicpc.net/problem/23832시간 제한메모리 제한solved.ac 티어1초512MB골드 1풀이 밀린 문제 정리하기. 이번에도 여전히 오일러 피함수이다. 이 문제는 1~N번 정점을 그래프로 만들 것이다. 이때 정점간에 간선을 만드는 조건은 정점 a, b가 각각 서로소여야 한다. 이때 간선의 개수를 구하는 문제이다. 나는 처음에 이게 오일러 피함수 문제인지 헷갈렸다. 서로소의 개수와 연관되이었다보니 오일러 피함수가 가능할 것 같다 생객해보다가 풀이를 떠올렸다. 문제가 조금 말이 어려워서 그렇지 조금 차근차근 풀어나가보자. 간선 없이 정점만 놓고 생각해보자. 임의의 정점 a는 a보다 큰 서로소인 정수와도 연결되어야 하고, a보다 작은 서로소와도 연결되어야 한다. a보..
문제https://www.acmicpc.net/problem/11689시간 제한메모리 제한solved.ac 티어1초256MB골드 1풀이 밀린 문제 정리하기, 오일러 피함수 문제는 계속된다. 오일러 피함수에 대해 계속 정리중이기 때문에, 해당 문제는 오일러 피함수 문제임을 바로 알 수 있다. 말이 수식으로 나와서 어려울수 있지만, 자연수 n에 대해 n 이하의 자연수 k가 GCD(n, k) = 1을 만족한다는 뜻은 n과 k는 서로소라는 뜻과 동치이다. 오일러 피함수는 n 이하의 n과 서로소인 자연수의 개수를 세는 함수이기 때문에 오일러 피함수를 사용하는 문제임을 알 수 있다.코드#include using namespace std;using ul = uint64_t;ul n;void sol() { ul res..
