Tags

51 pages

빠른 입출력

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

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

[Algorithm] C++ 백준 6171번: 땅따먹기 - 묶음 할인 최소 비용 DP+CHT

여러 직사각형 땅을 묶어 살 때 비용은 (묶음 내 최대 W)*(묶음 내 최대 H)입니다. W 오름차순 정렬 후 같은 W는 최대 H로 병합하고, 뒤에서 앞으로 보며 지배된 직사각형을 제거해 H를 단조 감소로 만듭니다. 이후 dp[i]=min(dp[k]+W[i]*H[k+1])를 단조 Convex Hull Trick으로 O(n)에 계산하며, 정수 교차 비교와 __int128 중간 연산으로 오버플로를 방지합니다.
[Algorithm] C++ 백준 6171번: 땅따먹기 - 묶음 할인 최소 비용 DP+CHT

[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

[Algorithm] C++ 백준 14737번 Dev, Please Add This!

격자에서 공을 상하좌우로 굴려 벽이나 가장자리에 닿을 때까지 이동하는 퍼즐에서, 모든 별을 하나의 플레이 순서로 획득할 수 있는지 판정한다. 단순 커버리지가 아니라 이동 순서 제약이 존재하므로 셀 단위 이동을 단방향 그래프로 모델링하고, 강한 연결 요소(SCC)로 압축한 DAG에서 상호 비가역(서로 도달 불가)한 컴포넌트 쌍의 동시 방문을 금지하는 제약과 각 별이 있는 칸의 행/열 중 하나의 정지 컴포넌트를 반드시 방문해야 한다는 제약을 2-SAT으로 구성해 모순 여부로 YES/NO를 결정한다. Kosaraju로 SCC를 구하고 DAG 도달성은 비트셋 DP로 처리하여 50×50까지 빠르게 동작한다.
[Algorithm] C++ 백준 14737번 Dev, Please Add This!