반응형
SMALL
백준 1715 카드 정렬하기
-
백준 1715번 카드 정렬하기알고리즘 2023. 3. 2. 11:30
문제 설명 A(10개)와 B(20개) 숫자 카드 묶음을 합치려면 각 묶음의 카드 개수를 더한 만큼의 비교횟수가 필요할 때, 여러 카드 묶음을 한 개로 합치려면 최소한 몇 번의 비교가 필요한지 구하는 문제입니다. 문제 풀이 아이디어 최소 비용으로 합치는 방법 10,20,40개의 숫자 묶음이 있을 경우를 생각해보도록 하겠습니다. 10,20을 먼저 합치고 40을 합칠 경우 10+20, 30+40 -> 총 30 + 70 = 100의 비용이 필요합니다. 10,40을 먼저 합치고 20을 합칠 경우 10+40, 50+20 -> 총 50 + 70 = 120의 비용이 필요합니다. 20, 40을 먼저 합치고 10을 합칠 경우 20+40, 60+10 -> 총 60 + 70 = 130의 비용이 필요합니다. 그렇다면 10,20..