문제

1차 풀이

처음 든 생각

• 가장 앞에 비교되는 것이, 가장 많이 반복되어 더해지므로
  가장 적은 수가 와야한다.
• 그 다음에도 그 다다음에도 마찬가지
• 그러므로 오름차순으로 정렬하고, 문제에서 요구하는 덧셈법칙대로 더하면 될 것이다.

1차 코드

n = int(input())

arr = []
for _ in range(n) :
	arr.append(int(input()))

arr.sort()

for i in range(n-1) :
	arr[i+1] = arr[i] + arr[i+1]

res = 0
for i in range(1, n) :
	res += arr[i]

print(res)

하하
아니 런타임도 아니고 틀릴것까진 없지않나 하하하
왜지..

정답 풀이

풀이 아이디어

항상 작은 크기의 두 카드 묶음을 합쳤을때 최적의 해를 보장한다.

가장 작은 원소를 순차적으로 꺼낼때, heap 을 떠올릴 수 있는가.

heap에 원소들을 넣어서 push와 pop에 O(logN)만큼의 빠르기로 정렬을 활용할 수 있는가

보고 든 생각

아니 그럼 첨 내가 생각한게 O(NlogN)이고
책 풀이는 시간복잡도가 Heap을 사용해서 O(logN)으로 구현하는거라서
내가 시간복잡도에서 약간 불리한거쥐,,
틀릴것까진 없지않나.......
n=0, n=1, n=2일때의 예외들 때문인가

2차 코드

n=0, n=1, n=2일때의 예외들을 추가했다.

n = int(input())

arr = []
for _ in range(n) :
	arr.append(int(input()))

arr.sort()

if len(arr) == 1 : # 원소가 하나일때
	print(arr[0])
elif  len(arr) == 2 : # 원소가 두개일때
	print(arr[0]+arr[1])
else :
	# 각 원소를 이전 원소들과 함께 정렬했을때의 연산 횟수로 초기화한다.
	for i in range(n-1) :
		arr[i+1] = arr[i] + arr[i+1]
	# 이렇게 해두고, 모든 원소를 더하면 모든 연산 횟수를 구할 수 있다.
	res = 0
	for i in range(1, n) :
		res += arr[i]

	print(res)

테스트케이스들은 통과하는데댕빡친다아놔진짜,,

정답 코드

import heapq

n = int(input())

# heap에 초기 카드 묶음을 모두 삽입
heap=[]
for i in range(n) :
	data = int(input())
	heapq.heappush(heap, data) # 복잡도 O(logN)

result = 0

# heap에 원소가 1개 남을때까지
while len(heap) != 1 :
	# 가장 작은 2개의 카드 묶음 꺼내기
	one = heapq.heappop(heap)
	two = heapq.heappop(heap)
	# 카드 묶음 합쳐서 다시 삽입 (내가 여기서 틀린듯!)
	sum_value = one+two
	result += sum_value
	heapq.heappush(heap, sum_value)

print(result)

틀린 이유

• 내풀이
  • 가장 작은 원소와, 두번째로 작은 원소를 합친 값은
    '그 중 제일 작음'이라고 생각했다.
    (예시에서 10,20,40이 있을때 10+20=30 한 값은 40보다 작았다.)
    이렇게 보장되지 않은 사실로 풀어서 오답이었다!

	one = heapq.heappop(heap)
	two = heapq.heappop(heap)
	# 카드 묶음 합쳐서 다시 삽입 (내가 여기서 틀린듯!)
	sum_value = one+two
	result += sum_value 
	heapq.heappush(heap, sum_value) ################

• 책 풀이
  • ######### 부분을 보면,
    가장 작은 원소와, 두번째로 작은 원소를 합친 값은
    '그 중 제일 작음'을 보장할 수 없으므로
    최소 경쟁에 참여시킨다. (=다시 힙에 집어넣는다.)

느낀점

주어진 테스트케이스로 문제를 파악하는 건 좋지만,,
원칙대로 생각합시다 아니면 좀 애먼 테스트케이스 여러 종류를 미리 떠올려봅시다

• 풀어두고 다른 테스트케이스 생각해서 조금 수정하는건 좋지만
  이번엔 다른 테스트케이스를 생각 못한 나머지 (원칙대로 이해안하고 테스트케이스를 건성으로 읽고 이해해서,, )아예 잘못된 풀이 방향을 잡아서 완전 틀려버렸다. 그러지맙시다!
• 비슷하게 주어진 테스트케이스는 통과하지만 오답인경우 이런 느낌으로 틀린게 아닌가 한번 첨부터 다시 짚어보자!!