16191

42JerryKim

42는 'The Hitchhiker's Guide to the Galaxy'라는 SF 소설에서 삶, 우주, 그리고 모든 것에 대한 궁극적인 질문에 대한 해답이다.

Home
Collections
Search
Categories
Tags
Archives
1. Dark Mode

Search

Categories

Algorithm BOJ CSharp Movie Design Patterns Shell Python Vocabulary Implementation Programming

Tags

Implementation SoftwareDevelopment C++ Programming Optimization SoftwareEngineering Algorithm Cpp BOJ 백준 Baekjoon 알고리즘 Performance 구현 Fast IO SoftwareArchitecture GNU++17 Problem-Solving 시간복잡도 Coding

Archives

Tags

1 page

16191

[Algorithm] C++ 백준 16191번 : Utilitarianism

트리에서 서로 인접하지 않는 k개의 간선을 골라 가중치 합을 최대로 만드는 문제. 라그랑주 최적화(λ)로 k-제약을 벌점으로 흡수하고, 노드별 상태 DP(A/B)로 F(λ)=max∑(w-λ)와 선택 간선 수를 O(n)에 계산, λ에 대한 단조성을 이용해 이분 탐색 후 F(λ)+λk의 최소값으로 정답을 복원한다.

[Algorithm] C++ 백준 16191번 : Utilitarianism

© 2018 - 2025 42JerryKim

Built with Hugo
Theme Stack designed by Jimmy