본문 바로가기

카테고리 없음

[백준 10090번] Counting Inversions (Python3)

def update(i):
  while i<M:
    fen[i] += 1
    i += i&-i

def sumfen(i):
  SUM = 0
  while i:
    SUM += fen[i]
    i -= i&-i
  return SUM

N = int(input()); M = 1<<20
data = [*map(int,input().split())]
nums = sorted([(-data[i],i+1) for i in range(N)])

fen = [0]*M; result = 0
for n,i in nums:
  result += sumfen(i)
  update(i)
print(result)

= 달리기 [백준 2517번] 달리기 (Python3) (tistory.com)

달리기 문제는 각각의 값을 구하고, 이 문제는 값들의 합을 구하면 된다.