Softeer [인증평가(4차)] 통근버스 출발 순서 검증하기 (난이도 3)

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
bus = list(map(int, input().split()))
arr = [[0 for i in range(n + 1)] for j in range(n + 1)]

for j in range(n - 1, -1, -1):
    for x in range(1, n + 1):
        if bus[j] < x:
            arr[x][j] = arr[x][j + 1] + 1
            # arr[X][j]는 j 번째 보다 오른쪽에 있는 버스들 중, x 보다 값이 작은 것들의 개수
        else:
            arr[x][j] = arr[x][j + 1]

ans = 0
for i in range(n):
    for j in range(i, n):
        if bus[i] < bus[j]:
            ans += arr[bus[i]][j]

print(ans)

알고리즘 유형

구간합

풀이 방법

[1]

임의의 자연수 X(1≤X≤N)에 대하여, arr[X][j]를 j 번째보다 오른쪽에 있는 숫자들 중,
X 보다 값이 작은 것들의 개수라고 정의할 수 있습니다.

각각의 X에 대해, j가 N일 때 N번째 보다 오른쪽에 있는 숫자는 없으므로,
arr[X][N] = 0이고, j 가 N-1일 때는 다음과 같이 계산이 가능합니다.

if bus[N - 1] < X:
   arr[X][j] = 1

이어서,

if bus[j] < X:
	arr[X][j] = arr[X][j+1] + 1

j가 1이 될 때까지 반복하므로, 총 시간복잡도는 O(N^2)입니다.

[2]

arr를 이용해서 정답 구하기

위에서 계산한 방법에 따라서 arr[bus[i]][j] 의 값은 j번째보다 오른쪽( j < k )에 있는 숫자들 중 bus[i] > bus[k] 인 것들의 개수입니다.

후기

이것이 난이도 3인가. 오늘도 조유리의 노래를 들으며 열심히 코딩 중.