[swea 3307-파이썬]최장 증가 부분 수열

swea 3307 최장 증가 부분 수열

사용언어 : PYTHON

풀이

백준에서 한 번 풀이를 했던 문제였다

dp를 사용해서 풀어야 하는데 점화식을 어떻게 세워야 할 지 잘 생각이 나지 않았다.

왜 점화식을 세우지 못했는지 풀이를 보고 알았다.

이 문제는 0~n까지 차례대로 dp리스트를 채운뒤 dp[n-1]이 정답이 되는것이 아닌 max(dp)가 정답이기 때문이었다.

dp[i] 는 l[i] (입력으로 받는 수열) 를 사용했을 때 생성될 수 있는 최장 증가 부분 수열의 길이이다

0 <= i < N 일 때 dp[i]는 (0 <= j < i) 일때 l[j] < l[i] 인 dp[j] 값 중 가장 큰 값 + 1 이다.

그러한 값이 없다면 1을 넣는다. (자기 자신)

그림으로 나타내면 다음과 같다

평소에 풀었던 dp의 방식과 접근 방법이 달라서 많이 헷갈린다.

잊지 않게 잘 기억해야겠다.

코드

def find_prev(n): # 인덱스가 i < n 인 dp리스트에서 l[i] < l[n]인 dp[i]값 중 가장 큰 값을 반환
    answer=[0]

    for j in range(n):
        if l[j]<l[n]:
            answer.append(dp[j])

    return max(answer)


def solve():
    for p in range(N):
        dp[p]=find_prev(p)+1


T=int(input())

for i in range(T):
    N=int(input())
    l=list(map(int,input().split()))
    dp=[0]*N
    solve()
    print(dp)
    print('#{} {}'.format((i+1),max(dp)))