[Platinum II] 가장 긴 증가하는 부분 수열 6 - 17411

문제 링크

성능 요약

메모리: 26244 KB, 시간: 816 ms

분류

이분 탐색, 자료 구조, 가장 긴 증가하는 부분 수열: O(n log n), 세그먼트 트리

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열과 개수를 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이고, 1개이다. A = {10, 20, 30, 10, 20, 30}인 경우에는 가장 긴 증가하는 부분 수열의 길이는 3이고, 4개가 있다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이와 개수를 출력한다. 개수는 매우 커질 수 있기 때문에 109+7로 나눈 나머지를 출력한다.

---

풀이

아이디어

참고자료

• 종만북
• velog - 가장 긴 증가하는 부분 수열 k
• 17411 풀이
• 네이버 블로그

과정
$k$번째 답을 구하는 문제를 풀기 위해서는 아래의 과정을 따른다.

• 답의 수를 세는 문제를 푼다.
• 답의 수를 기반으로 답안을 재구성한다.

이 문제는 단순히 답의 수를 세는 것이 아니라, 최대 증가 부분수열의 길이를 세어야 한다.
수열에는 무수히 많은 증가 부분수열이 존재할 수 있다. 이들 중 가장 긴 부분 문제를 찾아내는 과정은 최적화 문제이므로 아래 과정을 따른다.

• 바탕이 되는 최적화 문제를 푼다.
• 최적화 문제의 최적해를 세는 문제를 푼다.
• 답의 수를 기반으로 답안을 재구성한다.

따라서 아래 아이디어는 다음과 같다.
1. LIS를 찾는다 ($n\log{n}$ 이분탐색)
2. 각각의 수에서 LIS를 찾는다.

코드

import sys
import bisect

input = sys.stdin.readline
MOD = 1000000007

n = int(input())
S = list(map(int, input().split()))
c = [-float('INF')]
dp = [0] * n

for i in range(n):
    if c[-1] < S[i]:
        c.append(S[i])
        dp[i] = len(c) - 1

    else:
        pos = bisect.bisect_left(c, S[i])
        c[pos] = S[i]
        dp[i] = pos

cnt = len(c) - 1

summ = [[0] * (10001) for _ in range(cnt+1)]
num = [[0] * (n) for _ in range(cnt+1)]
for i in range(n-1, -1, -1):
    j = 1
    leng = dp[i]
    if leng < cnt:
        idx = bisect.bisect_right(num[leng+1], S[i]) - num[leng+1][0]
        j = summ[leng+1][-1] - summ[leng+1][idx]
    num[leng].append(S[i])
    summ[leng].append((j+summ[leng][-1]) % MOD)
    

print(cnt, (summ[1][-1] + MOD) % MOD)

---

회고

이 코드는 사실 동작하지 않는다. 메모리 초과로 인해 세그먼트 트리로 구현해야 한다고 하는데 세그먼트 트리를 모른다.. 나중에 세그먼트 트리를 공부하면 다시 한번 풀어볼 예정.