ps-BOJ

오랜만에 P5 푼 기념 풀이 과정 🔎 우선 주어지는 수열의 크기가 1,000,000이기 때문에 O(n^2)로는 안 된다는 건 금방 알 수 있다. 부분 수열 문제 자체도 좀 오랜만이긴 했지만 기억을 더듬어... O(n log n)으로 최장 증가 부분 수열의 길이를

풀이 과정 🔎 우선 조건을 만족하는 "K번 정점"에 대해 조금 더 이해해 보려고 했다. 문제에서는 이 정점이 루트가 되었을 때, 주어진 두 정점 A와 B의 "가장 가까운 공통 조상이 A이거나 B가 되지 않아야 한다"고 설명했다. 조금은 꼬아둔 설명이었던 것 같은데.

풀이 과정 🔎 가장 가까운 경우부터 체크하면서 도로를 추가해야 하는지, 다른 도로로 최소 이동 시간을 달성 가능한지 확인하면 어떨까 (주어진 게 최소 이동 시간이라고 해서 이런 생각이 들었던 듯) 이때, 확인되는 이동 시간에 따라 도로를 추가할지 결정하자. >

문제 참 길다 풀이 과정 🔎 해석해 보기 🤔 a. 하나의 노드를 (얼리 어답터가 아닌 사람으로) 선택했을 때, 해당 노드와 인접한 모든 노드는 무조건 얼리 어답터가 되어야 한다. b. (a)의 조건을 만족하면서 최대한 많은 노드를 선택했을 때, 선택되지 않은 노드의 수가 정답이다. c. 최대한 적은 노드를 얼리 어답터로 선택해서 모든 간선에 대해 ...