[인증평가(4차) 기출] 통근버스 출발 순서 검증하기 - lv3

문제

Softeer

Softeer

풀이

Softeer

Softeer

도저히 풀 수 없어 풀이를 봤다. 결국 DP 문제였는데, 버스 번호가 1 부터 N까지 자연수로 정해져 있다는 점에 착안하여 어떤 버스 번호 X와 주어진 배열 A 에서의 인덱스 j 에 대해서 dp[X][j] 를 j 번째 보다 오른쪽에 있는 번호들 중 X 보다 작은 번호들의 개수로 둔다. 여기서 i < j 를 만족시키면서 A 를 이중 순회하며 A[i] < A[j] 인 경우를 찾아내면 된다.

구간합 문제를 거의 풀어보질 않아서, 해설에서와 같이 이 문제가 구간합 유형이라는것은 이해하지 못하겠다.

N = int(input())
A = [0] + list(map(int,input().split()))
dp = [[0]*(N+1) for _ in range(N+1)]

answer = 0
for x in range(1,N+1):
    dp[x][N]=0
    dp[x][N-1] = 1 if A[N]<x else 0
    for j in range(N-2,0,-1):
        if(A[j+1]<x):
            dp[x][j] = dp[x][j+1] + 1  
        else: 
            dp[x][j] = dp[x][j+1]

for i in range(1,N-1):
    for j in range(i+1,N):
        if(A[i]<A[j]):
            answer+=dp[A[i]][j]


print(answer)