본문 바로가기

Problem Solving

(59)
[BOJ] 2472 체인점 굉장한 학생 문제랑 다익스트라의 짬뽕이다. 덕분에 코드가 장난아니게 길다.각 정점이 최대 5개의 간선을 가지니 다익스트라의 $O(ElgV)$ 시간복잡도가 $O(VlgV)$로 바뀐다. 그러면 주어진 세 정점에 대해서 다익스트라를 한번씩 돌려볼 수 있고, 모든 정점에 대해 주어진 세 정점으로부터 각 정점으로부터의 거리 $dist_i$가 나오게 된다. 거리의 범위는 크지만 대소관계만을 비교하면 되므로 등위를 정렬을 통해 다시 매겨주자. 그러면 굉장한 학생 문제처럼 모든 정점에 대해 체인점을 세울수 있음/없음을 판별할 수 있다. 그 이후 들어오는 쿼리는 $O(1)$에 처리 가능하다. 수행 시간은 다익스트라, 정렬, RMQ 등이 다 섞여서 결과적으로 $O(NlgN)$이다. 개인적으로 문제 자체도 굉장한 학생 문제..
[CF] Codeforces Round #464 (Div. 2) 이번 CF는 총 A~F의 6개 문제로 이루어져 있었다. ABCD 50분만에 다풀고 E 하려다가 도저히 못하겠어서 반쯤 던져놓고 있었는데 끝나기 2분 전에 B 해킹이 들어와서 11초 남기고 B번 마지막 서브미션해서 맞았다. 덕분에 점수도 개판되고 레이팅도 100오를거 50밖에 안올랐다. 그래도 D번을 10분만에 풀어내서 점수에 아아주 큰 타격은 안간듯. D번이 이렇게 쉬울 줄 알았으면 DABC 순서로 풀걸 그랬다. 다음은 내가 푼 문제에 대한 솔루션들.A. Love Triangle time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output As you could know ..
[BOJ] 1504 특정한 최단 경로 문제: https://www.acmicpc.net/problem/1504 그냥 다익스트라 몇번 돌리면 된다. 어차피 두 정점을 반드시 지나야 하는 것이라면 시작점->1번->2번->종점 아니면 시작점->2번->1번->종점 2가지 방법 안에서 반드시 최단경로는 나오게 되어 있다. 난이도는 1.75/5. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include #include #define INF (100000000) using namespace std; int n;vector lis[805]; vecto..
[BOJ] 1916 최소비용 구하기 문제: https://www.acmicpc.net/problem/1916 그냥 다익스트라 그 자체이다. 풀이를 설명할 필요가 있을까? 난이도는 1.5/5 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #include #define INF (2100000000) using namespace std; int main(){ int n,m,st,en; scanf("%d %d",&n,&m); priority_queue Q; vector lis(n+1,vector()); vector dist(n+1,INF); for(int i=0;idist[here]) continue; for(..
[BOJ] 13306 트리 문제: https://www.acmicpc.net/problem/13306 2016 KOI 중등부 3번 문제인 트리이다. 고등부 3번과 굉장히 비슷한 문제이기는 한데, 듣기로는 고등부 3번은 HLD라는 알고리즘을 써야 한다고 알고 있는데 이 문제는 상대적으로 깔끔하게 발상의 전환을 통해 문제를 해결할 수 있다. 실제로 대회장에 갔을 때도 모든 풀이는 다 생각해 놨는데 자료구조 구현을 못해서 실패했다. 웬만하면 풀이를 보기 전에 생각을 더 해봤으면 하는 좋은 문제. 내 해법은 Union-Find Tree로 알려져 있는 자료구조 (Disjoint Set)을 구현해서 문제를 역순으로 풀어 나가는 것이다. 어떤 정점과 그 정점의 부모 정점을 제거하면 그 두 트리는 분리되게 된다. 두 정점 사이에 경로가 존재하려..
[BOJ] 11052 붕어빵 판매하기 문제: https://www.acmicpc.net/problem/11052 너무 쉬워서 자세한 설명은 생략한다. 난이도는 그냥 1/5 123456789101112131415161718192021222324252627282930313233343536#include #include #include #define INF (987654321) using namespace std; int n;int cost[1005];int cache[1005][1005]; int dp(int b, int c){ if(b==0) return 0; if(c>n) return -INF; int &ret=cache[b][c]; if(ret!=-1) return ret; int ma=0; for(int i=c;i
[BOJ] 9466 텀 프로젝트 문제: https://www.acmicpc.net/problem/9466 내가 사이클에 무지하게 약하다는 것을 깨닫게 해준 문제다. 문제 자체는 특별할 게 없음에도 불구하고 이렇게 헤메는 걸 보면 망한 것 같다... 처음에 시작한 정점을 따로 체크해두고 처리하면 되는 문제였는데 코드를 좀 더 깔끔하게 짜 보겠다고 괜히 엉뚱하게 푼 것 같다. 보니까 다른 사람들도 다 이런 비슷한 방식으로 푼 것 같다. 만약 이미 사이클이 처리된 정점에 도달했다면 (색깔이 다르면) 그냥 바로 0을 반환하는 것으로 시간 초과를 막았다. 나는 개인적으로 1.75/5정도는 주고 싶은데 다른 사람들은 훨씬 쉽게 푼듯. 123456789101112131415161718192021222324252627282930313233343536..
[BOJ] 1992 쿼드 트리 문제: https://www.acmicpc.net/problem/1992 매우 쉬운 분할 정복 문제이다. 그냥 전구간이 하얀색/검은색인지 체크해서 분할하고 재귀함수로 넘겨주면 된다.사실 재귀함수에 인자를 4개 줄 필요도 없고 (핵심) 모두가 검은색/하얀색인지의 판정도 $O(n^2)$으로 미리 전처리 해두면 $O(1)$로 찾을 수 있다. 그렇지만 귀찮기도 하고 굳이 그렇게 할 이유가 없기에 생략. 가장 좋은 알고리즘은 문제를 가까스로 풀 수 있는 알고리즘이다. 코드는 다음과 같다. 좀 더럽긴 하다. 난이도는 1.25/5 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #includ..