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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

예제 입력 1

6
10 20 10 30 20 50

 

예제 출력 1

4

 

---

나의 코드

[Python(파이썬)]

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
dp = [1]*n	

for i in range(n):	# i : 비교하는 주체
    for j in range(i):	# j : 비교되는 대상
        if a[i] > a[j]:	# 비교되는 대상보다 주체가 증가한다면
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

 

---

풀이 

이 문제는 DP(다이나믹 프로그래밍)와 LIS(최장 증가수열)을 사용한 문제이다. 

 

 

• 값 저장 리스트(dp) 초기값

dp = [1] * n

dp 리스트의 초기값은 1로 지정한다.

이유는 dp에 저장할 숫자는 각 인덱스에 해당하는 개수에 따른 가장 긴 증가율 이다.

따라서 크기 비교하여 큰 증가율을 넣기 위해 초기값에는 본인만 포함하는 가장 작은 증가율인 1을 저장한다. 

 

 

• LIS 구현

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

 

예제

6
10 20 10 30 20 50

 

예제로 이 코드의 일부를 진행해 보면 (※ i를 5까지 돌려야하는데 3까지만 나타낸 그림)

 

 

i를 비교하는 주체라고 생각하고 for문을 j번(0~(i-1)) 돌려 i의 앞까지의 숫자와 비교한다. 

만약 a[i]가 a[j]보다 작다면 그냥 넘어가고 크다면(-> 증가하는 부분 수열의 조건을 성립) max(dp[i], dp[j]+1) 를 dp[i]에 대입한다. 

 

 

 

• max(dp[i], dp[j]+1)

dp[i] -> 현재 비교하는 주체의 dp에 저장되어있는 최장 수열 길이

dp[j] + 1 -> 비교되는 대상(j)의 dp에 저장되어있는 최장 수열 길이  +1 (현재 원소(a[i])가 a[j]보다 증가했기 때문)

 

 

 

---

문제 출처

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