BOJ 3000문제를 달성한 행복한 주입니다.
카카오 블라인드 1차
2시간 26분만에 7문제를 모두 풀었습니다. 문제가 공개된 이후에 풀이를 작성할 예정입니다.
BOJ 18944 Non-Decreasing Subarray Game
BOJ 19646 Random Generator
세그먼트 트리를 이용해 파라메트릭 서치를 하는 문제로, 수업용으로 좋은 문제인 것 같습니다.
BOJ 19650 개미여행, 2125 좀
똑같은 문제입니다.
풀이
BOJ 17677 케이크 3
BOJ 19619 자매 도시
슬픈 사연이 있는 문제입니다ㅠㅠ
풀이
BOJ 15939 쉬운 최단경로 문제
BOJ 15249 Building Bridges
BOJ 13058 Jewel Thief
특이한 냅색 응용 문제입니다.
최적해가 되는 위치가 단조성을 띄기 때문에 DnC Opt 사용해도 되고, 식을 잘 정리해보면 두 함수의 교점이 하나밖에 없기 때문에 Monotone Queue Opt나 Li Chao Tree를 사용해도 됩니다.
BOJ 15775 Voronoi Diagram
각 간선은 온전히 한 영역에 속하거나 절반으로 쪼개서 서로 다른 영역에 속하게 됩니다.
Multi-Source Dijkstra를 이용해서 문제를 풀 수 있습니다.
BOJ 18441 제곱 부분문자열
LCS를 $O(N^2/64)$ 정도에 구하는 방법은 왠지 모르게 잘 알려져 있습니다.
위 방법을 알고 있다면 $O(N^3/64)$ 풀이를 쉽게 찾을 수 있습니다.