[백준] 최대 공통 증가 수열(실패...) 7476 골1

오블챌을 위해 일단 풀 문제 선언만 하고 글 쓸게요...

다시 돌아와서 풀고 수정하겠습니다

 

요즘 본인의 부분수열 실력 부족에 심각성을 느끼고... 부분 수열 좀 백준에서 찾아 풀겠습니다

 

https://www.acmicpc.net/problem/7476

 

풀이로 곧 돌아오겠습니다 커밍쑨

 

----

 

일단 풀면서 LCS LIS 관련 문제임을 알게 되었고

 

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

 

이 포스트를 보면서

최장 공통 부분 수열의 길이를 구하는 방법과

DP를 역으로 탐색하면서, 그 수열 자체를 출력하는 방법도 알게 되었다

 

그러나 최장 공통 "증가" 부분 수열을 구하는 데 실패해서 일단 남겨두고 다른 문제를 먼저 풀고자 한다

 

실패한 코드는 아래와 같다

 

n = int(input())
a = list(map(int,input().split()))
m = int(input())
b = list(map(int,input().split()))

arr = [[0 for _ in range(m+1)] for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,m+1):
        if a[i-1]==b[j-1]:
            for k in range(i):
                if a[k - 1] < a[i - 1]:
                    arr[i][j] = max(arr[i][j], arr[k][j] + 1)
        else:
            arr[i][j] = max(arr[i-1][j], arr[i][j-1])
length = max(max(row) for row in arr)
print(length)
result=[]
x,y = n,m
while x > 0 and y > 0:
    if arr[x][y] == arr[x - 1][y]:
        x -= 1
    elif arr[x][y] == arr[x][y - 1]:
        y -= 1
    elif arr[x][y] == arr[x - 1][y - 1] + 1 and a[x - 1] == b[y - 1]:
        result.append(a[x - 1])
        x -= 1
        y -= 1
    else:
        x -= 1

print(*result[::-1])