[백준][python] 11053 가장 긴 증가하는 부분 수열문제

11053번: 가장 긴 증가하는 부분 수열

 

✏️ 내가 작성한 코드

N, A = int(input()), list(map(int,input().split()))

dp = [1]*N
for i in range(1,N): # dp[0]은 항상 1이므로 1부터 시작.
    for j in range(i):
        if A[j] < A[i]:
           dp[i] = max(dp[j]+1,dp[i])

print(max(dp))

 

✏️ 참고

dp 배열 : A[i]까지의 부분수열 최장길이를 dp[i]에 넣기 위한 것.

idx	0	1	2	3	4	5
A	10	20	10	30	20	50

A배열이 이렇게 존재하고 dp[3]을 구하려면?

 

1) A[0] 과 A[3]비교

→  A[3]더 크므로 dp[i] = max(dp[j]+1,dp[i]) 진행.

2) dp[3] = max(dp[0]+1,dp[3])

→  윗줄에서 A[0]보다 큰 걸 확인했으므로 A[0]의 dp값인 dp[0]보다 +1을 해주고, 현재 dp[3] =1 이랑 비교해서 max값을 dp[3]에 넣어줌

→  현재 dp[3] = 2

3) 다음 반복문 진행. A[1]과 A[3]비교 

→  A[3]더 크므로 dp[i] = max(dp[j]+1,dp[i]) 진행.

4) dp[3] = max(dp[1]+1,dp[3])

.

.

.

이런식으로 A[3]과 A[0], A[1], A[2]와 값의 크기를 비교해보고 해당 인덱스에 맞는 dp값을 비교해서 max로 뽑아오면 됨.

그럼 dp배열에는 A배열의 해당 인덱스까지의 최장 길이를 갖는 부분수열의 값들이 저장되고

거기서 또 max(dp)해서 가장 긴 값을 가져오면 된다.