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

문제

---

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

코드

---

My answer

import sys

input = sys.stdin.readline

n=int(input())
dp=[0]*n
dp[0]=1
array=list(map(int,input().split()))

for i in range(1,n):
    tmp=[dp[j] for j in range(i) if(array[j]<array[i])]
    if(tmp==[]):tmp.append(0)
    dp[i]=max(tmp)+1
#print(dp)
print(max(dp))

Another answer

n=int(input())
A=list(map(int,input().split()))
DP=[0]*(max(A)+1)
for i in range(n):
	DP[A[i]]=max(DP[:A[i]])+1
print(max(DP))

import sys
input=sys.stdin.readline

n=int(input())
num=list(map(int,input().split()))
dp=[1 for _ in range(n)]

for i in range(n):
    tmp=num[i]
    array=[0]
    for j in range(i):
        if(num[j]<tmp):
            array.append(dp[j])
    dp[i]=max(array)+1
#print(dp)
print(max(dp))

풀이

---

 

우선 문제를 이해하는데 좀 시간이 걸렸다. 가장 긴 증가하는 수열을 구하는 것인데, 무작정 지금까지 최대 길이의 수열만 저장하면 되는게 아니라, 전부 기록은 해둬야됐다. 좀 말이 어렵긴한데, 다양한 반례들을 보면서 이해하면 될 것 같다..

글 읽기 - 반례 모음집

내 풀이 방법은 우선 입력받은 숫자들을 돌면서, 현재 i보다 작은 숫자들 중 최대 길이를 보유한 것을 찾아 +1로 업데이트하는 방식이다. 

예를 들어, 10,20,50,10,11,12,13,14가 들어왔다고 해보자

우선 dp[0]=1로 초기화해뒀다.

dp[1]은 20 이전의 숫자들 중, dp에 저장된 길이들을 저장한다. 따라서 dp[0]의 1이 tmp에 들어가고, tmp중 max를 뽑아 20은 2가된다.

dp[2]는 50 이전의 숫자들 10,20의 dp인 1,2 중 max인 2에다가 1을 더해서 3이 된다.

dp[3]은 10 이전의 숫자들 중 10보다 작은 것들이 없어 tmp가 비기 때문에 tmp에다가 0을 넣어주고, 결과적으로 dp[3]=1이 된다.

dp[4]는 11이전의 숫자들 중 11보다 작은 10,20,10의 max인 2에다가 1을 더해서 dp[4]는 3이 된다.

이런식으로 업데이트하는 방식을 이용하였다.

 

another answer 1의 경우, 10이 들어오면 dp[0~10]중 즉 10보다 작은 것들의 개수를 세고 그 중 max에다가 1을 더해준다. 

다음 20이 들어오면 20보다 작은 값들은 현재 10이 있어서 2가 되고, 50이 들어오면 10,20이 들어와서 3이 되고, 11이 들어오면 2가되고, 12가 들어오면 3, 13이 들어오면 4가 되는 뭔가 계수정렬 방식?으로 푼 것 같다. 

another answer 2의 경우, 나와 동일한 방법이다.