[BOJ] 백준 11399 ATM (파이썬 python)

https://www.acmicpc.net/problem/11399

11399번: ATM

그리디 알고리즘, 삽입 정렬

인프런 강의를 보고 참고하였습니다~

 

 Step 1 문제 분석

ATM에서 모든 사람이 가장 빠른 시간에 인출하는 방법을 그리디 방식으로 해결한다.

ATM 앞에 있는 사람 중 인출 시간이 가장 적게 걸리는 사람이 먼저 인출할 수 있도록 순서를 정하는 것이 곧 그리디 방식이다. 이를 위해서는 인출 시간을 기준으로 값을 정렬해야한다. (오름차순)

 

정렬을 마친 후에는 각 사람이 돈을 인출하는데 필요한 시간을 더하면 된다. 

Step 2 수도코드 작성

사람의 수 N 입력받기

A(자릿수별로 구분해 저장한 리스트) 인출하는데 걸리는 시간 P 입력받기
S(A 합 배열: 각 사람이 인출을 완료하는데 필요한 시간 저장)

for i를 1 ~ N만큼 반복:

	for j를 i-1 ~ 0까지 뒤에서부터 반복:
    	현재 범위에서 삽입 위치 찾기
        
    for j를 i ~ insert_point + 1까지 뒤에서부터 반복:
    	삽입을 위해 삽입 위치에서 i까지 데이터를 한 칸씩 뒤로 밀기
    삽입 위치에 현재 데이터 저장

for i를 1 ~ N만큼 반복:
	A 리스트를 통한 합 배열 S 만들기

S 리스트의 각 데이터값을 모두 합해 결과 출력

 

Step3 코드 작성

# 백준 11399 ATM

#사람의 수 N 입력받기
N = int(input())

# A(자릿수별로 구분해 저장한 리스트) 인출하는데 걸리는 시간 P 입력받기
A = list(map(int,input().split()))

# S(A 합 배열: 각 사람이 인출을 완료하는데 필요한 시간 저장)
S = [0] * N

#for i를 1 ~ N만큼 반복:
for i in range(1,N):
  insert_point = 1
  insert_value = A[i]
  
  # for j를 i-1 ~ 0까지 뒤에서부터 반복: 현재 범위에서 삽입 위치 찾기
  for j in range(i-1,-1,-1):
    	
      if A[j] < A[i]: 
        insert_point = j+1
        break

      if j == 0:
        insert_point = 0
        
    # for j를 i ~ insert_point + 1까지 뒤에서부터 반복:
     # 삽입을 위해 삽입 위치에서 i까지 데이터를 한 칸씩 뒤로 밀기
  for j in range(i, insert_point, -1):
    A[j] = A[j-1] 
  A[insert_point] = insert_value

S[0] = A[0]

# A 리스트를 통한 합 배열 S 만들기
for i in range(1,N):
	S[i] = S[i-1] + A[i]

sum = 0
# S 리스트의 각 데이터값을 모두 합해 결과 출력

for i in range(0,N):
  sum += S[i]

print(sum)

 

 

 

 

• 참고자료 및 강의
• https://www.inflearn.com/course/lecture?courseSlug=%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC&unitId=148454