[백준] 11053번 가장 긴 증가하는 부분 수열(feat. 다이나믹 프로그래밍, LIS)

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

 

문제 접근

• 첫 번째 단계(문제 요약 및 조건 파악)

수열이 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하는 문제이다.

입력 조건은 수열의 크기 N은 1 <= N <= 1000 이다.
수열을 이루는 각 수x는 1 <= x <= 1000 이다.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 이 주어졌다고 가정해보자.
수열 A에서 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 으로 길이는 4이다.

 

• 두 번째 단계(문제 핵심 파악하기)

이 문제의 핵심은, DP 테이블을 선언하여, 앞서 계산한 값을 계속 이용해야 한다는 것이다.

그렇다면, DP테이블을 정의해 봐야 한다.
수열을 arr[], dp table을 dp[] 라고 가정하자.

그러면, dp[i]는 arr[i] 까지의 LIS 길이를 저장 하면 될 것이다.

예를 들어 아래와 같은 입력이 주어졌다고 가정해보자.

7
1000 10 20 10 30 20 50

그렇다면, 가장 긴 증가하는 부분 수열의 길이를 구하는 과정은 다음과 같을 것이다.

1000은 앞에 아무것도 없고, 현재로써는 증가하는 부분 수열로 인정할 수 있으므로, dp[0]에는 1을 저장한다.

10앞에는 1000이 있었다. 그런데, 1000보다는 10이 더작다. 그러면 10을 단독적인 증가하는 부분수열로 인정하여 dp[1]에 1을 저장한다.

20앞에는 1000과 10이 있다. 그런데, 20은 1000보다는 작다. 10보다는 크다. 현재 20의 dp테이블인 dp[2]에는 0이 저장되어 있고, 이는 dp[1] < dp[2]이다. 따라서, dp[2] = dp[1]을 해주고, dp[2] = dp[2] + 1을 해준다.

이 과정을 반복해서 50까지 탐색하면, dp테이블 갱신이 끝날 것이다.

그러면, dp테이블에서 max값을 반환하면 정답이 될 것이다.

'''
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성 해야한다.
ex) A = {10, 20, 10, 30, 20, 50}인 경우, LIS(Longest Increasing Subsequence)는
{10, 20, 30, 50} 이고, 길이는 4이다.

입력은 수열의 크기 N
둘째줄에는 수열을 이루고 있는 숫자들이 공백을 구분으로 주어진다.

i)
7
1000 10 20 10 30 20 50
이 입력에 대해서 생각을 해보자.

dp_table을 만들고,
arr과 인덱스를 맞춰서 dp[i]에는 arr[i] 숫자까지의 최장 증가 부분 수열 개수 저장할 것이다.

arr[0]인 1000을 먼저 보면, 앞에 아무것도 없으므로, dp[0]에 dp[0] + 1을 저장 한다. - > dp[0] = 1

arr[1]인 10을 보면, 앞에는 1000이 있다. 1000 < arr[1]은 false이므로  dp[1] = dp[1] + 1 을 한다. -> dp[1] = 1

arr[2]인 20을 보면, 앞에는 1000과 10이 있다. 1000<arr[2]은 false다. 10 < arr[2]은 true이고, dp[2] < dp[1]는 true 이므로 dp[2] = dp[1]을 하고, 1000과 10을 다 확인 했으므로 dp[2] = dp[2] + 1을 해준다. -> dp[2] = 2

arr[3]인 10을 보면, 앞에는 1000과 10, 20이 있다. 1000<arr[3]은 false다. 10 < arr[3]는 false다. 20 < arr[3]은 false다. 1000과 10과 20을 다 확인했으므로 dp[2] = dp[2] + 1을 해준다. -> dp[3] = 1

arr[4]인 30을 보면, 앞에는 1000과, 10, 20, 10 이 있다. 1000<arr[4]는 false다 10 < arr[4]는 true 이고, dp[4] < dp[1] 는 true이므로 dp[4] = dp[1] 을 한다. 그리고  20 < arr[4] 는 trye이고, dp[4] < dp[2] 는 true이므로 dp[4] = dp[2] 를 해준다.  10 < arr[4]는 true이고, dp[4] < dp[3] 은 false이다. 다 확인했으므로, dp[4] = do[4] + 1 -> dp[4] = 3

arr[5]인 20을 보면, 앞에는 1000과, 10, 20, 10, 30이 있다. 1000 < arr[5]는 false다. 10 < arr[5]는 true이고, dp[5] < dp[1]은 true 이므로 dp[5] = dp[1]을 한다. 그리고 20 < arr[5]는 false이다. 10 < arr[5]는 true이고, dp[5] < dp[1]은 false이다. 30 < arr[5]는 false이다. 다 확인했으므로, dp[5] = dp[5] + 1 -> dp[5] = 2

arr[6]인 50을 보면, 앞에는 1000과 10, 20, 10, 30, 20이 있다. 1000< arr[6]은 false다. 10 < arr[6]은 true이고, d[6] < dp[1]은 ture 이므로 d[6] = dp[1]을 한다. 그리고 20 < arr[5]는 ture 이고, dp[6] < dp[2]는 이므로 dp[6] = dp[2]를 한다. 10 < arr[6]은 true이고, dp[6] < dp[3]은 false이다. 30 < arr[6]은 true이고, dp[6] < dp[4] 은 true이므로 dp[6] = dp[4]를 해준다. 20 < arr[6]은 true이고, dp[6] < dp[5]는 false이다. 다 확인했으므로, dp[6] = dp[6] + 1 -> 4

최종 dp_table은 [1, 1, 2, 1, 3, 2, 4] 이다. 여기서 max값을 뽑아주면 구하고자하는 답이 된다.


'''

 

코드 작성

 

import sys

n = int(sys.stdin.readline().rstrip())
arr = list(map(int, sys.stdin.readline().rstrip().split()))
dp = [0 for i in range(n)]

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

print(max(dp))

DP문제는 DP테이블을 어떻게 정의하느냐가 관건.