✅ BOJ 30805 - LCS(Longest Common Subsequence)

사전 순 최대 공통 부분 수열 (백준 30805)

두 수열 A, B에서 공통 부분 수열 중 사전 순으로 가장 큰 걸 찾는 문제.

 

핵심은 그리디. 매 단계마다 현재 A와 B의 남은 구간에서 공통으로 등장하는 수 중 가장 큰 수 하나를 고름.

숫자 범위가 작기 때문에(1~100) 이게 가능함. 찾은 수는 정답 리스트에 추가하고, 다음 탐색은 그 숫자 이후부터 다시 시작.

 

list.index(val, start)로 탐색 시작 지점을 유지하면서 부분 수열 조건 지킴. 슬라이싱은 안 쓰고 인덱스만 넘겨서 성능 유지.

더 이상 공통되는 수를 찾을 수 없으면 종료. 최종적으로 정답 수열 길이와 값들을 출력하면 됨.

---

#최장길이 공통수열 Longest Common Subsequence
import sys
input=sys.stdin.readline

def find_max_value(a,b,a_start_idx,b_start_idx):
    max_val=-1
    for a_num in a[a_start_idx:]:
        for b_num in b[b_start_idx:]:
            if a_num==b_num:
                if a_num>max_val:
                    max_val=a_num
                break
    return max_val if max_val!=-1 else False

def find_max_common_subsequence(a,b):
    a_start_idx=0
    b_start_idx=0
    answer=[]
    while True:
        max_common_value=find_max_value(a,b,a_start_idx,b_start_idx)
        if not max_common_value:
            break
        answer.append(max_common_value)
        a_start_idx=a.index(max_common_value,a_start_idx)+1
        b_start_idx=b.index(max_common_value,b_start_idx)+1
    
    return answer

def main():
    n=int(input().strip())
    a=list(map(int,input().split()))
    m=int(input().strip())
    b=list(map(int,input().split()))
    
    answer=find_max_common_subsequence(a,b)
    print(len(answer))
    print(' '.join(map(str,answer)))
    
if __name__=="__main__":
    main()

 

max_value 찾고 그 값 기준으로 리스트의 뒤 원소만 보게 하면서, 이를 반복하기만 하면 되는 문제였는데 LCS 구하는 문제인 줄 알고 헷갈려서 좀 많이 헤멤. 아이디어 안 떠오르면 꽤나 스트레스 받는 문제.