-
11399. [Python]ATMPython_알고리즘/Silver IV 2023. 1. 26. 11:01
1. 문제
https://www.acmicpc.net/problem/11399
11399번: ATM
첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)
www.acmicpc.net
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 256MB
- 낮은 수 정렬
3. 파이썬 코드
N = int(input()) # 결과값 출력할 변수 선언 total_min = 0 num_list = list(map(int,input().split())) # 리스트 정렬 num_list.sort() # 중간값 변수 설정 check = 0 for i in num_list: check += i total_min += check print(total_min)
4. 문제를 풀고난 후 생각
- 최소한의 시간을 들여야 하는문제로 시간들이 누적합이 적용되어 그 값이 제일 작을때를 출력하는 문제이다.
- 최소한의 시간이 소요될려면 시간들의 배치가 어떻게 되어야 최소한의 시간이 나오는지 생각해 봐야한다.
- [5, 2, 1, 3, 6] 이라는 리스트가 들어올 경우 앞사람이 걸린 시간이 계속해서 더해져 나가기 때문에 앞사람이 걸린시간이 최소한이 되었을때 맨 마지막 사람이 걸리는 시간이 제일 적게 걸리는 것을 알 수 있다.
- 예를 들어 [2, 1, 6, 3, 5] 라는 순으로 배치가 되었을경우 P1 = 2, P2 = 3, P3 = 9, P4 = 12, P5 = 17 분이 걸리며 총합 43분이 소요된다. 하지만 낮은 수부터 배치하여 리스트를 만들었을 경우 [1, 2, 3, 5, 6] 라는 리스트가 나오고 P1 = 1, P2 = 3, P3 = 6, P4 = 11, P5 = 17 총합 38분 으로 제일 최소의 시간이 소요되는 것을 볼 수 있다.
- 문제를 풀때 문제를 읽고 어떤식으로 규칙이 적용되는지를 먼저 찾으면 쉽게 풀 수 있다.
5. 문제를 푸는데 도움이 되는 지식
- 리스트 정렬
'Python_알고리즘 > Silver IV' 카테고리의 다른 글
1789. [Python]수들의 합 (0) 2023.01.30 11047. [Python]동전 0 (0) 2023.01.30 2217. [Python]로프 (0) 2023.01.29 1459. [Python]걷기 (0) 2023.01.25 2839. [Python]설탕 배달 (0) 2023.01.23