JJaewon의 PS하는 블로그

Class 8을 달았다.Class 8에 처음? 등장하는 FFT / 플로우 / DnC opt 등을 공부하긴 귀찮고 그렇다고 국메기같은 굉장한 문제를 짜긴 싫어서, 최대한 구현이 편해보이고 이미 알고 있는 지식으로 풀 수 있는 문제들을 열심히 찾아서 풀었더니 딱 20문제가 됐다.  풀면서 재미 또는 감동이 있었던 문제에 대해 간략하게 사고과정과 풀이를 작성한다. 레드 블루 스패닝 트리 #4792더보기파란색 간선을 최소로 써서 MST를 만들어 그때 파란색 간선이 몇개인지 세고,파란색 간선을 최대로 써서 MST를 만들어 그때 파란색 간선이 몇개인지 세면,그 사이에 개수가 답이 될 수 있다. 풀이 자체는 n년 전부터 알고 있었는데, 이왕 푸는거 증명까지 해보기로 했다.현재 MST에 파란색 간선이 x개 있을 때, ..

4.2 ~ 4.11 동안 푼 문제 정리 산만한 고양이 https://www.acmicpc.net/problem/14866 DFS 스패닝 트리를 만들고 Tree DP 느낌으로 서브트리 내부의 Back Edge들을 잘 카운트하고 케이스 분류하면 각 정점의 자식들을 확인하면서 사이클을 제거할 수 있는지 판단 가능하다. The Bridege on the River Kawaii https://www.acmicpc.net/problem/16695 처음 보면 좀 무서운데, $V