[백준] ATM(11399)

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

N의 최댓값이 1,000이고 시간제한이 1초이므로 $O(N^2)$ 이하인 시간복잡도 알고리즘 중 아무거나 사용해도 된다.

돈을 뽑는데 시간이 가장 적게 걸리는 사람부터 오름차순으로 정렬한 후 합 배열 공식을 통해 모두 더하면 시간의 합의 최솟값을 구할 수 있다.

정렬을 위해 그냥 sort() 함수 써도 되지만 연습삼아 여기서는 삽입정렬을 사용해보도록 하겠다.

삽입정렬이란 선택한 데이터를 정렬할 범위 내에서 삽입할 위치를 찾아 데이터를 삽입하는 것이다.

삽입정렬의 알고리즘 순서는 다음과 같다.

1. 가장 최초에 정렬 대상값으로 지정하는 현재값을 처음에서 2번째에 위치한 값으로 지정한다.

2. 현재값을 기준으로 왼쪽부터 역순으로 탐색하면서
   2-1. 삽입하려는 값(현재값)이 탐색 중인 값보다 크면 그 다음 위치에 삽입한 후, break를 통해 탐색을 종료한다.

   2-2. 만약 배열의 첫번째 인덱스까지 갔지만 위치를 찾지 못한경우 배열의 맨 앞으로 삽입한다.
   (배열에서 크기가 가장 작은 원소라는 의미)

3. 삽입 위치까지 데이터를 한 칸씩 뒤로 이동한다.

4. 삽입 위치에 값을 삽입한다.

1, 2, 3, 4번 과정을 배열의 길이만큼 반복한다.

import sys

input = sys.stdin.readline

N = int(input())
P = list(map(int, input().split()))

# 삽입정렬 알고리즘 사용
for i in range(1, N):
    insert_point = i # 현재값이 삽입될 위치
    insert_value = P[i] # 현재값

    # 현재 값을 기준으로 왼쪽부터 역순으로 탐색
    for j in range(i - 1, -1, -1):
        if P[i] > P[j]: # 삽입하려는 값이 탐색 중인 값보다 크면
            insert_point = j + 1 # 그 다음 위치에 삽입
            break # 삽입 위치를 찾았으므로 반복 종료

        if j == 0: # 끝까지(배열의 첫번째 인덱스까지) 갔지만 위치를 못찾은 경우
            insert_point = 0 # 배열의 맨 앞으로 삽입
    
    for j in range(i, insert_point, -1): # 삽입 위치까지 데이터를 한 칸씩 뒤로 이동
        P[j] = P[j-1]
    P[insert_point] = insert_value # 삽입 위치에 값 삽입

# 리스트 P의 합 배열 S
S = [0] * N
S[0] = P[0]

# 합 배열 생성
for i in range(1, N):
    S[i] = S[i-1] + P[i]

print(sum(S))