일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 파이썬
- 영어 회화
- 영어기초
- 블록체인
- 라이브아카데미
- BFS
- 다이나믹프로그래밍
- N-Queens
- python
- baekjoon
- Hyperledger Fabric
- 일상회화
- 관계절
- IF
- 회화
- Backtracking Algorithm
- 알고리즘
- dfs
- 영어
- 라이브 아카데미
- used to
- 백트래킹
- 백준
- 영어회화
- 백트래킹 알고리즘
- 영어회와
- 회화기초
- 전치사
- 정렬
- 완전탐색
Archives
- Today
- Total
내 맴
[ 백준 ] 11399번 : ATM (파이썬) 본문
728x90
문제 )
https://www.acmicpc.net/problem/11399
[ 풀이 ]
✔ Greedy Algorithm을 사용하여 풀어준다.
< Greedy Algorithm이란? >
결정을 해 야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 solution으로 선택함으로써
최종 solution에 도달하는 Algorithm이다.
각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하기 위해서는 돈을 인출하는 데 걸리는 시간인 P(i) 가 작은 순서대로 돈을 뽑아야한다.
그러므로, P(i)의 list를 오름차순으로 정렬한 순서대로 돈을 뽑으면 돈을 인출하는데 시간의 합의 최솟값을 구할 수 있다.
< Totaltime Function의 Algorithm >
✔ P(i)의 list → arr
✔ 돈 인출하는 데 걸리는 시간의 총 합 → total
✔ 1사람이 돈을 인출하는 데 걸리는 시간 → person
1. arr을 오름차순으로 정렬한다
2. arr의 원소에 하나씩 접근한다 → i
Ⅰ. i번째 사람이 돈을 인출하는 데 걸리는 시간(person)을 구한다
Ⅱ. i번째 사람까지의 걸리는 시간의 합(total)을 구한다.
- python code
import sys
input=sys.stdin.readline
def Totaltime(arr):
arr.sort() # 오름차순으로 정렬
total=0 # i번째 사람까지의 걸리는 시간의 합(total)
person=0 # i번째 사람이 돈을 인출하는 데 걸리는 시간
for i in arr:
person+=i
total+=person
return total
N= int(input())
p=list(map(int,input().split()))
print(Totaltime(p))
728x90
'Algorithm > Baekjoon 문제풀이' 카테고리의 다른 글
[ 백준 ] 9663번 : N-Queen (파이썬) (0) | 2020.05.07 |
---|---|
[ 백준 ] 1541번 : 잃어버린 괄호 (파이썬) (0) | 2020.04.27 |
[ 백준 ] 1931번 : 회의실배정 (파이썬) (0) | 2020.04.23 |
[ BAEKJOON ] No. 11047 동전 0 (0) | 2020.04.23 |
[ BAEKJOON ] No. 5430 AC (0) | 2020.04.21 |