[백준 11053번-파이썬]가장 긴 증가하는 부분 수열

백준 (BOJ) 11053번
https://www.acmicpc.net/problem/11053

사용언어 : PYTHON

1.문제

2.풀이

A={10,20,10,30,20,50}을 예로 들어 생각해보았다.

dp[i] = A[0], A[1], … A[i] 일때 ‘증가하는 부분 수열’에서 A[i]의 위치(인덱스)값 이다.

• i=0 일 때 dp[0]는
  A[0] 즉 10의 ‘증가하는 부분 수열’={10} 에서 위치 즉 1 이다.
• i=1 일 때 dp[1]는
  A[1] 즉 20의 ‘증가하는 부분 수열’={10,20} 에서 위치 즉 2 이다.
• i=2 일 때 dp[2]는
  A[2] 즉 10의 ‘증가하는 부분 수열’={10,20} 에서 위치 즉 1 이다.
• i=3 일 때 dp[3]는
  A[3] 즉 30의 ‘증가하는 부분 수열’={10,20,30} 에서 위치 즉 3 이다.
• i=4 일 때 dp[4]는
  A[4] 즉 20의 ‘증가하는 부분 수열’={10,20,30} 에서 위치 즉 2 이다.
• i=5 일 때 dp[5]는
  A[5] 즉 50의 ‘증가하는 부분 수열’={10,20,30,50} 에서 위치 즉 4 이다.

가장 긴 증가하는 부분 수열의 길이는 max(dp) 즉 4가 된다.

---

A={10,15,20,1,2,3,4,5,30,27}을 예로 들어 생각해보았다.

• i=0 일 때 dp[0]는
  A[0] 즉 10의 ‘증가하는 부분 수열’={10} 에서 위치 즉 1 이다.
• i=1 일 때 dp[1]는
  A[1] 즉 15의 ‘증가하는 부분 수열’={10,15} 에서 위치 즉 2 이다.
• i=2 일 때 dp[2]는
  A[2] 즉 20의 ‘증가하는 부분 수열’={10,15,20} 에서 위치 즉 3 이다.
• i=3 일 때 dp[3]는
  A[3] 즉 1의 ‘증가하는 부분 수열’={1} 에서 위치 즉 1 이다.
• i=4 일 때 dp[4]는
  A[4] 즉 2의 ‘증가하는 부분 수열’={1,2} 에서 위치 즉 2 이다.
• i=5 일 때 dp[5]는
  A[5] 즉 3의 ‘증가는는 부분 수열’={1,2,3} 에서 위치 즉 3 이다.
• i=6 일 때 dp[6]는
  A[6] 즉 4의 ‘증가하는 부분 수열’={1,2,3,4} 에서 위치 즉 4 이다.
• i=7 일 때 dp[7]는
  A[7] 즉 5의 ‘증가하는 부분 수열’={1,2,3,4,5} 에서 위치 즉 5 이다.
• i=8 일 때 dp[8]는
  A[8] 즉 30의 ‘증가하는 부분 수열’={1,2,3,4,5,30} 에서 위치 즉 6 이다.
• i=9 일 때 dp[9]는
  A[9] 즉 27의 ‘증가하는 부분 수열’={1,2,3,4,5,27} 에서 위치 즉 6 이다.

가장 긴 증가하는 부분 수열의 길이는 max(dp) 즉 6이 된다.

2-1.순환식을 세우기

2-2.base case로 수렴하는지 확인

k가 없으면 dp[i]+=1인 base case로 수렴한다

2-3.순환식을 계산

dp배열은 d[0]=1, 나머지는 0으로 초기화 했다.

20보다 작으면서 dp값은 큰 dp[0]+1

만족하는 k가 없으므로 자기자신 + 1

30보다 작으면서 dp값은 큰 dp[1]+1

20보다 작으면서 dp값은 큰 dp[2]+1

50보다 작으면서 dp값은 큰 dp[3]+1

3.코드

dp + 1 연산은 모두 수행하기 때문에 안쪽 for문 밖으로 +1연산을 뺐다.

import sys
input = sys.stdin.readline

N=int(input())

p=list(map(int,input().split()))

dp=[0]*N
dp[0]=1

for i in range(1,N):
  for j in range(i):
    if(p[j]<p[i] and dp[j]>dp[i]):
      dp[i]=dp[j]
  dp[i]+=1

print(max(dp))