[C++] 백준/Silver/15903. 카드 합체 놀이
·
C++/Algorithm
문제: 카드 합체 놀이 (백준 15903번)문제 분석N장의 카드가 있고, 각 카드에 적힌 숫자가 주어진다.카드 합체 놀이에서는, 매번 두 장의 카드를 골라 그 합을 계산한 뒤, 두 카드 모두 그 합으로 교체한다.이를 총 M번 반복한 후, 모든 카드에 적힌 숫자의 합을 구하는 문제이다.핵심 포인트:최소 힙 활용:매 번 가장 작은 두 수를 선택하면, 앞으로의 합산 결과가 최소가 되어 최종 결과에 큰 영향을 미치게 된다.그래서 최소 힙(우선순위 큐)를 사용하여 O(M log N)의 효율적인 계산을 할 수 있다.알고리즘 흐름:모든 카드 값을 최소 힙에 넣는다.M번 동안, 힙에서 가장 작은 두 수를 꺼내 합을 구하고, 그 합을 다시 힙에 두 번 넣는다.모든 연산이 끝나면 힙에 남은 모든 카드의 값을 합산한다.전체..