https://www.acmicpc.net/problem/1715
1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장
www.acmicpc.net
이 문제는 이렇게 쉽다고?? 이런 생각이 들었던 문제 같다.
첫째 줄에 카드의 개수가 주어진다. 둘째 줄부터는 카드가 주어진다.
ex) 카드가 10,20,40 이렇게 주어지면 (10 + 20) + (30 + 40) 이렇게 계산을 한다.
이것을 보고 카드를 오름차순으로 정렬을 하고 리스트를 하나 만든 뒤, 더한 값을 리스트에 추가할 생각을 했다.
|
1
2
3
4
|
heap = []
num = int(input())
for i in range(num):
heapq.heappush(heap,int(input()))
|
cs |
heap이라는 리스트를 만든 뒤, for 반복문을 이용해서 heap에 최소 힙을 준수해서 숫자들을 넣었다.
만약 heapq 모듈을 모른다면 https://solution-is-here.tistory.com/114
백준(S2) 11279번: 최대 힙(파이썬, Python3)및 heapq 설명
https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열
solution-is-here.tistory.com
이 사이트를 보고 오길 바란다.
|
1
2
3
4
5
6
7
8
9
10
|
result_list = []
while heap:
if len(heap) == 1:
break
else:
first = heapq.heappop(heap)
second = heapq.heappop(heap)
third = first + second
result_list.append(third)
heapq.heappush(heap,third)
|
cs |
그 후, heap의 길이가 1이 되면 종료 하는 while 반복문을 만들었다.
heap의 길이가 1이 아니면 heap에서 heappop 함수를 이용해서 가장 작은 함수 2개를 추출한 뒤 더한 값을 result_list에 넣어주고 heappush 함수를 이용해서 heap에 넣어줬다.
|
1
2
3
4
|
result = 0
for i in range(len(result_list)):
result += result_list[i]
print(result)
|
cs |
result_list의 길이만큼 반복하는 반복문에서 result라는 변수에 result_list의 값들을 더해줬다.
그다음 출력하면 끝이다.
정답코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
import sys
import heapq
input = sys.stdin.readline
heap = []
num = int(input())
for i in range(num):
heapq.heappush(heap,int(input()))
result_list = []
while heap:
if len(heap) == 1:
break
else:
first = heapq.heappop(heap)
second = heapq.heappop(heap)
third = first + second
result_list.append(third)
heapq.heappush(heap,third)
result = 0
for i in range(len(result_list)):
result += result_list[i]
print(result)
|
cs |