26_카드 정렬하기 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 happenundo.tistory.com
카드정렬하기
1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 카드 비교 횟수가 최소가 되는 총 비교횟수를 출력하면 되는 문제다. 처음에 문제를 읽고, 이게 골드4문제라고? 라는 생각이 들었다. 그래서 5분만에 구현하고 제출하니 바로 시간 초과가 떴다. 문제를 자세히 읽어보니 입력 크기가 최대 100,000개 이므로 단순 비교로는 O(N^2)이라서 당연히 시간 초과가 뜬다. 그래서 계속 고민을 해봤다. 고민하다 보니, 이런 규칙이 나왔다. 매번 합칠 카드 묶음을 정할 때, 카드 묶음 리스트 중 가장 작은 값 ..
