[알고리즘/동적 계획법] 11053번 : 가장 긴 증가하는 부분 수- python

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

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

 

---

• 문제
• 소요시간: 실패

---

• 설계하기(접근방법) 

1. 수열 크기와 수열을 입력받는다

2. 알고리즘 해석

이전의 값들과 비교하여, 자신보다 작은 수(중복되지 않은)들의 집합 + 자신의 수를 더한 것이

가장 긴 부분 증가수열이다

 

ex) 30 -> 10,20 + 30 -> 3

ex) 50 -> 10,20,30 + 50 -> 4

 

수의 값은 비교하기 쉬우나, 중복되지 않게 제어할 수 있는 장치가 하나 필요하다.

dp를 이용하면 가능하다

 

for문을 이중 순회하면서 자신의 원소와 그 전의 모든 원소를 비교하고 dp를 저장한다

for i in range(n):

      for j in range(i):

 

만약 a[i](현재 원소) > a[j](이전의 원소) 라면 이 첫 번째 조건이다

또한 현재 원소의 dp값은 이전의 원소 中, 자신보다 작은 값에서 최대값보다 1이 클 것이기에

dp[i] < dp[j] 인 경우

dp[i] = dp[j]를 해준다 (자신보다 작은 값이 자기보다 dp가 크면 그 값을 dp[i]로 바꿔준다)

 

그 후 자기 자신을 포함한 부분수열이니 +1을 해준다.

 

3. dp값중 가장 큰 값(max)를 출력한다

 

 

 

 

 

 

 

 

---

• 코드(출력)

n = int(input())
a = list(map(int, input().split()))

dp = [0 for _ in range(n)]

for i in range(n):
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1

print(max(dp))

---

• 얻어갈 부분

1. 아이디어가 아예 떠오르지 않는 동적 계획법 문제였다. 만약 이런 경우, 어떻게 해법을 찾을 것인지 고민해보자