[백준][그리디][재귀] 30805. 사전 순 최대 공통 부분 수열

30805. 사전 순 최대 공통 부분 수열

 

 

• 풀이
  • 첫번째 수부터 순서대로 가장 큰 수여야 함
  • 길이가 가장 길어야 하니까 가능한대로 큰 수를 계속 뽑아야함
    • → 가장 큰 수를 뽑은 이후, 그 이후 배열들에서 계속해서 큰 수를 뽑아야함
    • 재귀

n = int(input())
alst = list(map(int, input().split()))
m = int(input())
blst = list(map(int, input().split()))


def solution(a, b, result):
    if (not a) or (not b):
        return result

    tmp1 = max(a)
    tmp2 = max(b)

    idx1 = a.index(tmp1)
    idx2 = b.index(tmp2)

    if tmp1 == tmp2:
        result.append(tmp1)
        solution(a[idx1+1:], b[idx2+1:], result)
    elif tmp1 > tmp2:
        a.pop(idx1)
        solution(a, b, result)
    else:
        b.pop(idx2)
        solution(a, b, result)


result = []
solution(alst, blst, result)

print(len(result))
print(*result)

• 주의📍
  • 인덱스를 찾고 pop을 할때 alst가 아닌 재귀적으로 받은 a,b 에서 찾아야함