[백준 13555번] 증가하는 부분 수열 (Python3)

def update(i,v):
  while i<M:
    fen[i] += v; fen[i] %= mod
    i += i&-i

def cal(i):
  s = 0
  while i:
    s += fen[i]; s %= mod
    i -= i&-i
  return s

def solve():
  arr = [0]*(N+1)
  for i in range(1,M):
    for id in idx[i]:
      arr[id] = cal(id)
    for id in idx[i]:
      update(id,count[id])
  return arr

N,K = map(int,input().split()); M = 1<<17; mod = 5*10**6
seq = [*map(int,input().split())]
idx = [[] for i in range(M)]
for i in range(N):
  idx[seq[i]].append(i+1)
count = [0]+[1]*N
for _ in range(K-1):
  fen = [0]*M
  count = solve()
print(sum(count)%mod)

= [백준 17409번] 증가 수열의 개수 (Python3) (tistory.com)

딱 하나의 차이점은 중복되는 숫자가 존재한다는 것인데, 인덱스를 sort로 구하지 않고 각 값에 넣은 뒤 같은 숫자는 합을 모두 구한 후, update를 한꺼번에 하는 방식으로 해결할 수 있다.