BOJ 11053번 : 가장 긴 증가하는 부분 수열 (Python/Silver 2)

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

---

설명

부분 수열의 최대 길이를 구해야 하는 문제이다. 부분 수열이란 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열이다. 쉽게 말해서 이전 수보다 크면 수열이 이루어진다. 흔히 수학에서 보았던 두 항의 차이가 일정한 등차수열을 말하는 것이 아니다. 

 

예를 들어, A : { 10, 20, 10, 30, 20, 50 } 이라는 수열이 있을 때, 부분 수열은 A : { 10, 20, 10, 30, 20, 50 } 이고, 최대 길이는 4이다.

 

풀이

 

Dynamic Programming으로 풀어야 하는 문제이다. 이전 문제를 가지고 재사용해서 풀어야 한다.

 

풀이 1

반복문을 돌려주면서 현재 값(i)이 이전 값(j)보다 크면,

dp에서의 현재 위치(i)와 이전 위치(j)에서 +1을 해준 카운트 값과 비교하여

더 큰 카운트 값을 현재 위치(i)에 저장해준다. 이렇게 하면 지금껏 카운트 했던 값 중 큰 값을 저장하면서 수열의 최댓값을 알 수 있는 것이다.

최종으로 결과를 출력할 때 dp에 저장되어 있는 값에서 최댓값을 출력한다.

 

풀이 2

현재 값이(i)이 이전 값(j)보다 크면서, dp에서의 현재 위치(i)가 이전 위치(j)보다 카운트 수가 작으면

이전 위치(j)의 카운트 값을 현재 위치(i)에 저장한다.

이전 위치와의 비교가 끝났으면 현재 위치(i)에 +1을 해주며 count해준다.

 

사실 글로만 보면 이해가 잘 안 가기 때문에 코드 한 줄 한 줄에 변수를 넣어가며 풀어보는 것이 좋을 것 같다. 

Solution

풀이 1

import sys
input = sys.stdin.readline

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

for i in range(N):
    for j in range(i):
        if num[i] > num[j]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

풀이 2

import sys
input = sys.stdin.readline

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

for i in range(N):
    for j in range(i):
        if num[i] > num[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1
print(max(dp))