[백준 13711번] LCS 4 (Python3)

def updateseg(i,v,start,end,x):
  if start==end:
    seg[x] = v
  else:
    mid = (start+end)//2
    if i <= mid:
      seg[x] = max(seg[x],updateseg(i,v,start,mid,x*2))
    else:
      seg[x] = max(seg[x],updateseg(i,v,mid+1,end,x*2+1))
  return seg[x]

def maxseg(i,start,end,x):
  if i == end:
    return seg[x]
  mid = (start+end)//2
  if i <= mid:
    return maxseg(i,start,mid,x*2)
  return max(seg[x*2],maxseg(i,mid+1,end,x*2+1))

N = int(input())
seq1,seq2 = [[*map(lambda x:int(x)-1,input().split())] for i in range(2)]

Index = [0]*N
for i in range(N):
  Index[seq2[i]] = i

seg = [0]*4*N
for i in range(N):
  n = seq1[i]
  idx = Index[n]
  updateseg(idx,maxseg(idx,0,N-1,1)+1,0,N-1,1)

print(max(seg))

세그먼트 트리로 해결하였다.

LCS https://www.acmicpc.net/problem/9251 문제를 어떻게 풀었는지 기억해 보면 알고리즘은 다음과 같다.

1. 두 수열을 seq1, seq2로 둘 때, seq2와 길이가 같은 DP 배열을 만든다.

2. seq1의 글자를 순서대로 seq2와 같은 글자를 찾는다.

3. 같은 글자를 찾으면, 현재의 인덱스 이전까지 가장 큰 DP값 +1로 DP를 갱신한다.

 

나는 이 문제를 세그먼트 트리로 해결할 수 있겠다고 판단하였다.

간단하게 설명하면,

1. seq2의 위치에 대한 인덱스를 미리 저장하여 위의 2번 과정을 O(1)로 처리한다.

2. 위의 3번 과정에서 max값을 찾는것을 세그먼트 트리로 O(logN)으로 처리한다.

따라서 전체 시간복잡도 O(NlogN)만에 수행할 수 있게된다.

 

참고로 문제를 해결한 후 태그를 확인하였는데, LIS (가장 긴 증가하는 부분수열) 로 푸는 문제라는 것을 알게되었다.

그러자 "와 이런 방식도 있었겠구나" 하는 생각이 들었다. 짐작컨대 seq1의 숫자의 순서대로 seq2의 숫자를 바꾸고, seq2의 LIS를 찾는 방식으로 해결하지 않을까 생각한다.

 

 

오늘의 교훈) 세그먼트 트리는 매우 유용하다