[백준] 30805 사전 순 최대 공통 부분 수열

문제

어떤 수열이 다른 수열의 부분 수열이라는 것은 다음을 의미합니다.

• 해당 수열의 원소들이 다른 수열 내에서 순서대로 등장합니다.
• 예를 들어, $\{1,1,5\}$는 $\{3,\underline{\color{blue} 1} ,4,\underline{\color{blue} 1} ,\underline{\color{blue} 5} ,9\}$의 부분 수열이지만, $\{1,5,1\}$의 부분 수열은 아닙니다.

또한, 어떤 수열이 다른 수열보다 사전 순으로 나중이라는 것은 다음을 의미합니다.

• 두 수열 중 첫 번째 수가 큰 쪽은 사전 순으로 나중입니다.
• 두 수열의 첫 번째 수가 같다면, 첫 번째 수를 빼고 두 수열을 다시 비교했을 때 사전 순으로 나중인 쪽이 사전 순으로 나중입니다.
• 길이가 $0$인 수열과 다른 수열을 비교하면, 다른 수열이 사전 순으로 나중입니다.

양의 정수로 이루어진 길이가 $N$인 수열 $\{A_1,\cdots ,A_N\}$이 주어집니다. 마찬가지로 양의 정수로 이루어진 길이가 $M$인 수열 $\{B_1,\cdots ,B_M\}$이 주어집니다.

수열 $A$와 수열 $B$가 공통으로 갖는 부분 수열들 중 사전 순으로 가장 나중인 것을 구하세요.

입력

첫 줄에 수열 $A$의 길이 $N$이 주어집니다. $(1 \le N \le 100)$ 
둘째 줄에 $N$개의 양의 정수 $A_1,A_2,\cdots,A_N$이 주어집니다. $(1 \le A_i \le 100)$ 
셋째 줄에 수열 $B$의 길이 $M$이 주어집니다. $(1 \le M \le 100)$ 
넷째 줄에 $M$개의 양의 정수 $B_1,B_2,\cdots,B_M$이 주어집니다. $(1 \le B_i \le 100)$ 

출력

$A$와 $B$의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 크기 $K$를 출력하세요.
$K \ne 0$이라면, 다음 줄에 $K$개의 수를 공백으로 구분해 출력하세요. $i$번째 수는 $A$와 $B$의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 $i$번째 수입니다.

내 풀이

import sys
input = sys.stdin.readline

n = int(input())
list1 = list(map(int, input().split()))
m = int(input())
list2 = list(map(int, input().split()))

dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        if list1[i-1]==list2[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

max1 = dp[n][m]
common = []
for i in range(max1):
    id = dp[-1].index(i+1)
    common.append(list2[id-1])

max2 = max(common)
id = common.index(max2)
answer = common[id:]

print(len(answer))
print(*answer)

위는 LCS를 이용해서 풀어보려다가 오답 처리된 코드이다. 하지만 어느 반례 때문에 실패한 것인지 잘 모르겠다...

아래는 다른 풀이를 참고하여 고쳐 풀어서 정답을 받은 코드이다.

import sys
input = sys.stdin.readline

n = int(input())
list1 = list(map(int, input().split()))
m = int(input())
list2 = list(map(int, input().split()))

common = set(list1)&set(list2)

answer = []
while common:
    max1 = max(common)
    answer.append(max1)
    
    idx1 = list1.index(max1)
    idx2 = list2.index(max1)
    
    list1 = list1[idx1+1:]
    list2 = list2[idx2+1:]
    
    common = set(list1)&set(list2)
    
print(len(answer))
print(*answer) 

코멘트

결국에는 사전 순으로 가장 나중인 것을 구해야 하므로 처음부터 정석적으로 최장 공통 수열을 구할 필요는 없다. 우선 두 수열에서 공통인 수들을 뽑아내서 max 값을 기준으로 common 배열이 빌 때까지 인덱싱을 하며 공통 부분이 있는지 반복적으로 찾으면 두 수열의 공통 부분 수열 중 사전 순으로 가장 나중인 것을 찾을 수 있게 된다.

References

https://www.acmicpc.net/problem/30805
https://code-angie.tistory.com/63