[Baekjoon/🥈SilverⅢ] 11399: ATM

Intro

• 문제는 비교적 길지만 핵심은 세 번째 문단에 나와있다.
  

• 문제를 요약한다면 다음과 같다.

  • N명의 사람이 모두 돈을 인출하고자 한다.
  • N명의 사람이 각각 돈을 인출하는데 걸리는 시간이 주어진다.
    • 1번, 2번 사람이 돈을 인출하는데 걸리는 시간이 각각 1분과 2분이라 하자.
    • 1번 사람은 돈을 인출하기까지 1분이 소요된다.
    • 2번 사람이 돈을 인출하기까지 걸리는 시간은 대기시간 1분과 인출시간 2분을 합한 3분이 된다.
  • 줄을 서는 순서에 따라서, 모든 사람이 돈을 인출하는데 걸리는 시간이 달라진다.

• 최종적으로 N명의 사람이 모두 돈을 인출하는데 걸리는 최소의 시간을 구하면 된다.

접근 방법🙋‍♀️

모든 사람이 돈을 인출하는데 최소의 시간이 걸리기 위해서는 각 사람들이 대기하는 시간을 줄여야 한다.

👩 만약 돈을 인출하는데 가장 오래 걸리는 사람의 순서가 빠르다고 생각해보자!!

• 뒤에 있는 사람들의 대기 시간이 앞 사람 인출 시간만큼 길어지게 된다.

따라서 사람들의 대기시간을 줄이기 위해서는 인출하는데 걸리는 시간이 적은 사람을 먼저 인출하도록 하는 것이다.

Algoritm👩‍💻

위 접근 방식을 바탕으로 작성한 코드를 분석해보자.

👩 예를 들어 주어진 시간들이 다음과 같다고 가정하자. ([3, 1, 4, 3, 2])

• 시간을 오름차순으로 정렬한다. ([1, 2, 3, 3, 4])
• 전체 걸리는 시간에 각 시간은 다음과 같이 영향을 준다.
  • 1은 첫 번째 사람을 포함한 모든 사람이 인출하는데 걸리는 시간에 포함된다.
  • 2는 첫 번째 사람을 제외한, 두 번째 사람을 포함한 모든 사람이 인출하는데 걸리는 시간에 포함된다.

👩 결론적으로 최솟값은 다음과 같은 형식으로 구해진다.

(최솟값을 delay라는 변수에 저장한다.)

• delay += 1 * 5
• delay += 2 * 4
• delay += 3 * 3
• delay += 3 * 2
• delay += 4 * 1
• delay = 32

#21.10.04
N = int(input())
time = list(map(int, input().split()))
time.sort()
delay = 0
i = N-1
for j in range(1, N+1):
  delay += time[i] * j
  i -= 1
print(delay)

👩 이번 문제는 매우 간단하게 해결됐다!!히히

코드가 간단해 추가 설명은 하지 않도록 한다.

끝! ~(˘▾˘~)