DP 썸네일형 리스트형 BOJ 25392 - 사건의 지평선 (D3) 사용 알고리즘 Segment Tree + SCC + 위상정렬 dp 풀이 일단 어떻게 했는진 몰라도 i->L~R 간선을 잘 이어줬다고 치자. 무한 번 표시된다 = 사이클에서 돌고 있다는 의미이다. 따라서 사이클 내부에서 가장 큰 원소를 찾으면 그 사이클 내부에서의 정답이 된다. 단 어떤 사이클 u에서 v로 간선이 있는경우, u에서의 정답은 max(u 내부에서의 정답, v 내부에서의 정답)이다. 따라서 위상정렬 dp로 순차적으로 사이클에서의 최댓값을 결정해나가면 된다. 이제 i->L~R 간선을 깔끔하게 처리하는 법만 생각하면 된다. L~R은 구간이다. 구간 크기가 O(N)이므로 간선이 최대 O(N^2)개가 생긴다. 그렇다면 구간을 O(logN) 정도로 표현할 수 있다면 추가해야 하는 간선은 O(NlogN)개.. 더보기 BOJ 4013 - ATM (P2) https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net 사용 알고리즘 SCC + 위상정렬 DP 풀이 ATM에서 현금을 인출할 때, 어떤 정점에서 사이클이 존재한다면 그 사이클을 쭉 돌면서 사이클에 속하는 모든 정점의 ATM을 이용할 수 있다. 따라서 사이클 내의 정점들을 묶어 생각할 수 있고, 하나의 SCC로 묶어줄 수 있음을 알 수 있다. 예제 그래프이다. 위에 적힌 숫자는 ATM에서 인출할 수 있는 현금이고, 색칠된 숫자는 그 정점에.. 더보기 이전 1 다음
