Algorithm/백준
[Do it! 알고리즘] ATM 인출 시간 계산하기(백준 11399)
potato_pizza
2024. 3. 9. 20:00
728x90
Do it! 알고리즘 코딩테스트
삽입 정렬
정의
- 삽입 정렬: 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식
삽입 정렬 수행 방식
- 현재 index에 있는 데이터 값을 선택
- 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색
- 삽입 위치부터 index에 있는 위치까지 shift연산 수행
- 삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산 수행
- 전체 데이터의 크기만큼 index가 커질 때까지 즉 선택할 데이터가 없을때까지 반복
ATM 인출 시간 계산하기(백준 11399)
https://www.acmicpc.net/problem/11399
문제
코드
import sys
input = sys.stdin.readline
N = int(input())
lst = list(map(int, input().split()))
sum = [0] * N
for i in range(1, N):
ins_pt = i
ins_val = lst[i]
for j in range(i-1, -1, -1):
if lst[j] < lst[i]:
ins_pt = j + 1
break
if j == 0:
ins_pt = 0
for j in range(i, ins_pt, -1):
lst[j] = lst[j-1]
lst[ins_pt] = ins_val
sum[0] = lst[0]
for i in range(1, N):
sum[i] = sum[i-1] + lst[i]
answer = 0
for i in range(0, N):
answer += sum[i]
print(answer)
References
728x90
반응형