🗨️ Comment
- 문제파악하기
-
같은 작업을 반복한다
-
그런데 정해진 횟수만큼 작업을 끝낸 후, 마지막엔 최솟값을 가지고자 한다
-
그럼 매 작업마다 최솟값을 가지도록 하자
→ 두 개의 최솟값 고르는 방법?
⇒ 제일 쉽게 정렬 떠올리기
⇒ 시간복잡도 확인 : ok
-
🍯 python의 sort()메소드의 시간복잡도
- sort 함수는 입력의 크기가 커질 경우 효율적으로 정렬하기 위해 퀵 정렬과 같은 진화된 정렬 방식을 사용하기 때문에 O(N log N)의 시간 복잡도를 가짐
⏰ 시간복잡도 계산하기
- n(2 ≤ n ≤ 1,000) → card리스트의 최대길이가 1000
for _ in range(m)→ m의 최댓값은 0 ≤ m ≤ 15×n → 0 ≤ m ≤ 15000
card.sort()⇒ card리스트 한번 정렬 → sort()의 시간복잡도는 O(NlogN)
- sum 메소드 → 한 번 순회 → O(n)
👉 O(m nlogn) + O(n) ⇒ O(mnlogn) ( 1초 제한안에 들어온다 )
🥳 정답코드
# 1초 / 512MB
# 자연수가 적힌 카드n장
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
card = list(map(int, input().split()))
for _ in range(m):
# 정렬
card.sort()
# [0], [1] 의 값 더해서, 덮기
tmp = card[0] + card[1]
card[0] = tmp
card[1] = tmp
print(sum(card))