[백준 17409번] 증가 수열의 개수 (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 idx:
    arr[i] = cal(i)
    update(i,count[i])
  return arr

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

팬윅트리+DP로 해결하였다.

기본적인 풀이 아이디어는 달리기 [백준 2517번] 달리기 (Python3) (tistory.com) 와 동일하다. 수열이 작은 인덱스부터 채우면서 앞쪽에 현재 숫자보다 작은 숫자가 몇 개 있는지를 확인하면 된다.

이때 현재 숫자에서 뒤에 존재하는 길이가 K인 부분수열은 현재 이전에 존재하는 길이 K-1의 부분수열의 합이라 할 수 있다. 따라서 이를 DP로 해결할 수 있다.

달리기 문제에서 약간의 추가 아이디어가 필요한 문제

 

 

오늘의 교훈) 팬윅트리는 유용하다.