[백준 18785] Clock Tree
문제 https://www.acmicpc.net/problem/18785 알고리즘 DFS 풀이 Bessie가 트리위에 주어진 맵을 이동해가며 시계를 조정할 때, 모든 시계가 가르키는 시간이 12시가 되도록 할수 있는 방의 시작갯수를 구하는 문제입니다. 임의의 출발지에서 모든 노드가 12가 될 수 있는지를 확인하는 것이 목표입니다. $N$제한이 2500이므로 $O(N^2)$에 근접하는 알고리즘을 떠올려봅시다. 첫 번째로는 리프노드의 시간을 12시로 맞추기 위해서는 무조건 리프노드와 리프노드의 부모를 계속해서 왔다갔다 해야지만 리프노드를 원하는 숫자 12로 맞출 수 있습니다. 12로 설정된 리프노드는 우리의 관심사 밖이므로 제거되고 리프노드의 부모였던 노드는 새로운 리프노드가 됩니다. 위 시뮬레이션을 계속 ..
Algorithm
2021. 5. 16. 15:46
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- spring
- 이분매칭
- 이분탐색
- union find
- Suffix Array
- 동적계획법
- Oracle
- dijkstra
- string
- DP
- hld
- SCC
- 트라이
- greedy
- Fenwick
- sorting
- dfs
- sweeping
- 정렬
- 2-SAT
- bfs
- kmp
- Segment tree
- 펜윅트리
- 좌표압축
- spring boot
- 스위핑
- implementation
- knapsack
- 세그먼트트리
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
글 보관함