주제
Sparse table로 LCA를 구하면서 조상까지의 최장·최단 도로를 함께 DP로 저장해, 각 쿼리를 O(log N)에 처리합니다.
동전 1의 풀이를 확장해, 금액별 최소 동전 개수를 DP로 갱신하고 만들 수 없는 경우를 처리합니다.
1차원 DP로 메모리 초과를 피하면서, 동전별로 금액 1~k를 갱신해 O(nk)에 경우의 수를 구합니다.
whyz
