Tags

21 pages

Long Long

[Algorithm] cpp 백준 18227번: 성대나라의 물탱크

루트 C에서 시작하는 트리에서 "A 도시에 물 채우기"는 루트→A 경로의 각 정점 v에 깊이(v)+1 리터를 더합니다. 따라서 임의의 정점 v의 물의 양은 서브트리(v)에서 발생한 갱신 횟수 × (깊이(v)+1)로 환원됩니다. 오일러 투어로 트리를 평탄화하고 펜윅 트리(BIT)로 서브트리 구간의 갱신·질의를 처리해 O((N+Q)logN)에 해결합니다. 경계 입력과 64-bit 오버플로를 주의합니다.
[Algorithm] cpp 백준 18227번: 성대나라의 물탱크

[Algorithm] C++ 백준 12736번 : Fireworks

백준 12736 Fireworks(APIO 2016)는 스위치-연결점-폭약으로 이루어진 트리에서 모든 폭약의 폭발 시각을 같게 만들기 위해 도화선 길이를 조정하는 최소 비용을 구하는 문제입니다. 볼록 함수(slope trick) 기반 트리 DP와 small-to-large 우선순위 큐 합병으로 O((N+M) log^2(N+M))에 해결합니다. 구현 핵심은 기울기 변화 지점을 우선순위 큐로 관리하고, 간선 통과 시 upperize 연산으로 기울기와 절편 변화를 반영하는 것입니다. 안전한 64-bit 정수 사용과 서브트리 크기 기준 정렬로 상수 시간을 줄여 AC를 얻습니다.
[Algorithm] C++ 백준 12736번 : Fireworks