[백준]11053 가장 긴 증가하는 부분 수열(Python)

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

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

 

문제 접근

 

만약 특정수를 기준으로 나보다 작은 친구를 세는 것은 비효율적이므로 dp로 접근해야 한다고 생각 

dp는 결국 점화식을 어떻게 세우느냐가 핵심

지난번 연속합 문제를 생각해 보면 점화식을 만들 때 정의를 명확하게 하는 것이 중요한 것 같다.  

i 번째를 포함해서 만드는 지의 여부가 중요

 

연속합 문제의 경우 i번째를 포함해서 만들 수 있는 부분합의 최대라면,

이 문제의 경우 i번째를 포함해서 만들 수 있는 부분 수열 길이의 최댓값을 구하자

 

ex) [10, 20, 10, 30, 20, 50] => 4

1. 첫 번째 원소 10은 이전 원소가 없기에 1 =>  [1, 1, 1, 1, 1, 1]

 

2. i=1, j=0

두 번째 원소 20은 이전 원소 10보다 크기 때문에 10 다음 20이 올 수 있으므로, dp[1]을 dp[0]+1인 2로 갱신

=> [1, 2, 1, 1, 1, 1]

 

3. i=2, j=0  /  i=2, j=1

세 번째 원소 10은 첫 번째 원소 10과 같으므로 dp[2]는 갱신x 두 번째 원소 20보다 작으므로 dp[2] 역시 갱신x

=> [1, 2, 1, 1, 1, 1]

 

4. i=3, j=0  /  i=3, j=1  /  i=3, j=2

네 번째 원소 30은 첫 번째 원소 10보다 크기 때문에 dp[3] = max(dp[3], dp[0]+1) => [1, 2, 1, 2, 1, 1]

네 번째 원소 30은 두 번째 원소 20보다 크기 때문에 dp[3] = max(dp[3], dp[1]+1) => [1, 2, 1, 3, 1, 1]

네 번째 원소 30은 세 번째 원소 10보다 크기 때문에 dp[3] = max(dp[3], dp[2]+1) => [1, 2, 1, 3, 1, 1]

 

5. i=4, j=0  / i=4, j=1  / i=4,j=2  / i=4,j=3  

다섯 번째 원소 20은 첫 번째 원소 10보다 크기 때문에 dp[4] = max(dp[4], dp[0]+1) => [1, 2, 1, 3, 2, 1]

다섯 번째 원소 20은 두 번째 원소 20보다 크지 않으므로 갱신x

다섯 번째 원소 20은 세 번째 원소 10보다 크기 때문에 dp[4] = max(dp[4], dp[2]+1) => [1, 2, 1, 3, 2, 1]

다섯 번째 원소 20은 네 번째 원소 30보다 크지 않으므로 갱신x

 

6. i=5, j=0  /  i=5, j=1  /  i=5, j=2  /  i=5, j=3  / i=5, j=4  

여섯 번째 원소 50은 첫 번째 원소 10보다 크기 때문에 dp[5] = max(dp[5], dp[0]+1) => [1, 2, 1, 3, 2, 2]

여섯 번째 원소 50은 두 번째 원소 20보다 크기 때문에 dp[5] = max(dp[5], dp[1]+1) => [1, 2, 1, 3, 2, 3]

여섯 번째 원소 50은 세 번째 원소 10보다 크기 때문에 dp[5] = max(dp[5], dp[2]+1) => [1, 2, 1, 3, 2, 3]

여섯 번째 원소 50은 네 번째 원소 30보다 크기 때문에 dp[5] = max(dp[5], dp[3]+1) => [1, 2, 1, 3, 2, 4]

여섯 번째 원소 50은 다섯 번째 원소 20보다 크기 때문에 dp[5] = max(dp[5], dp[3]+1) => [1, 2, 1, 3, 2, 4]

 

이 중 가장 max값을 출력!!

 

코드

 

첫 시도..!!

import sys
input = sys.stdin.readline

N = int(input())

A = list(map(int, input().split()))
dp = [0]*N

dp[0] = 1

if A[0] <=  A[1]:
    dp[1] = 2


for i in range(2, N):
    if A[i-1] <= A[i] :
        dp[i] = dp[i-1] + 1
    else:
        dp[i] = dp[i-1]
    # print(dp[i])
print(dp[N-1])

 

import sys
input = sys.stdin.readline

N = int(input())

A = list(map(int, input().split()))
dp = [1]*N

dp[0] = 1

for i in range(1, N):
    for j in range(i):
        if A[j] < A[i]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

 

문제 회고

 

DP 문제를 풀면서 점화식의 기준을 명확히 해야 생각이 꼬이지 않는다는 것을 알게 되었다.

이 문제에서 DP 테이블의 기준은 'i번째 원소를 포함하여 만들 수 있는 최대 증가 부분 수열의 길이'이다.