[BOJ-17409]증가 수열의 개수(in Python)

문제

https://www.acmicpc.net/problem/17409

17409번: 증가 수열의 개수

 

설명

가장 긴 증가하는 부분 수열 문제는 파이썬 풀이가 있지만,

증가 수열의 개수(17409)는 파이썬 풀이를 찾으려고 해도 찾기가 힘들어서

lastknight00님의 포스트를 참고하여 Python 코드로 작성하였습니다.

N이 작은 경우에는 DP를 이용한 풀이가 가능하지만 시간복잡도가 O(N^2)으로

위 문제의 조건(1<=N<+100,000)에서는 적용하면 시간초과 판정을 받습니다.

아래 코드는 DP를 이용하는 것은 동일하나 각 원소보다 작은 수의 개수를 조회할 떄

세그먼트 트리를 이용하여 시간복잡도 O(KNlogN)로 작동합니다.

lastknight00님의 c++코드와 로직은 동일합니다.

 

소스 코드

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
arr = list(map(int, input().split()))
dp = [[0] * int(n + 2) for _ in range(m + 1)]

def q(p, k):
    s = 0
    while p:
        s = (s + dp[k][p]) % 1000000007
        p -= (p & -p)
    return s

def u(p, k, v):
    while p <= n + 1:
        dp[k][p] = (dp[k][p] + v) % 1000000007
        p += (p & -p)

u(1, 0, 1)
for i in arr:
    for j in range(1, m + 1):
        u(i + 1, j, q(i, j - 1))

print(q(n + 1, m))

 

Reference

- https://lastknight00.tistory.com/11

[백준] 증가 수열의 갯수(17409)

- https://m.blog.naver.com/PostView.naver?blogId=edenooo&logNo=221624562330&proxyReferer=https:%2F%2Fwww.google.com%2F 

백준(BOJ) 새로 추가된 8문제 풀이

- https://www.geeksforgeeks.org/count-number-increasing-subsequences-size-k/

Count number of increasing subsequences of size k - GeeksforGeeks

- https://hrothgar.tistory.com/69

BOJ 13555 증가하는 부분 수열

- https://www.geeksforgeeks.org/count-number-increasing-subsequences-size-k/

Count number of increasing subsequences of size k - GeeksforGeeks