글 읽기 - 7476번 최대 공통 증가 부분 수열

mongsiry013 9년 전 0

그냥 일반적인 dp 방법인데..

어느 때 오답 판정이 나오는질 모르겠네요.

랜덤 케이스 몇개 만들어서 돌려보아도 틀린 경우를 못 찾겠더라구요.

일단 코드 설명은

수열 A,B를 입력 받고

A[0]과 B[0] 에 마이너스 무한대 값을 추가.

N는 A의 길이, M은 B의 길이.

dp(a,b) 는 수열 A[a:]와 B[b:]의 최대 공통 부분 수열을 리스트로 리턴해주는 함수입니다.

def dp(a, b) :
    global cache
    if cache[a][b] != -1 : return cache[a][b]
    cache[a][b] = []
    for i in range(a+1, N) :
        if A[a] < A[i] :
            if A[i] in B[b+1:] :
                candi = dp(i, b+1+B[b+1:].index(A[i]))
                if len(candi) > len(cache[a][b]) :
                    cache[a][b] = candi[:]
    cache[a][b].insert(0, A[a])
    return cache[a][b]

N = int(input())+1
A = [-float("INF")]+list(map(int, input().split()))
M = int(input())+1
B = [-float("INF")]+list(map(int, input().split()))

cache = [[-1]*M for i in range(N)]

ans = dp(0,0)
ans.pop(0)
print(len(ans))
for i in ans :
    print(i, end = ' ')
if ans : print()

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

7476번 최대 공통 증가 부분 수열

mongsiry013 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말