문제 이해 💬

백준 #11399 ATM

ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하시오.
줄을 서는 순서에 따라 전체 시간 합이 달라진다.

시간 합 구하는 법
P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 일때
순서대로 뽑으면 3+4+8+11+13 = 39분
[P2=1, P5=2, P1=3, P4=3, P3=4] 순서로 줄을 서면, 1+3+6+9+13 = 32분

처음 든 생각 😀

가장 적은시간의 총 합
= 앞순서일수록,( 많이 중복되어 더해지니까) 작은 수가 제일 많이 더해지게 되고,
뒷 순서일수록 (제일 적게 중복되어 더해지니까) 큰 수가 제일 적게 중복되어 더해지도록 하면 이게 제일 적은 최적해 아닌가?

그럼 오름차순으로 정렬시켜 더하면 그게 최솟값 아닌가?
이렇게 간단할 일이 있나..? 보장가능한가?
너무 자명해서 보장하기보다 복잡도를 고려해야할 것 같다.

복잡도
가장 시간이 많이 걸리는건 정렬 O(NlogN)이니 복잡도 ㄱㅊ

공식화

피보나치로 각자 Pi 를 구하는건 비효율적으로 보인다.

다음같이 Pi * (배열 길이-i) 를 구하면
일일이 모든 원소를 피보나치로 구하고, 또 그걸 전부 더해서 답을 구하는 것 보다 좀 더 적은 계산으로 구할 수 있을 것 같다.

피보나치 수열의 시간복잡도는 O(2^N) 이고,
위의 공식으로 구하는 복잡도는 [O(N)]이니 이게 된다면 더 좋은 더하기 식인것같다.

코드 1회차 👩🏻‍💻

# 모든 사람들의 출금 전체 시간을 계산한다
def calc(arr, n) :
  res = 0
  for i in range(n) : res += arr[i] * (n-i)
  return res

n = int(input())
A = list(map(int,input().split()))
A.sort() # 오름차순으로 정렬
print(calc(A, n))

통과!