[백준 | 실버2] 11053본 가장 긴 증가하는 부분 수열(LIS)

https://www.acmicpc.net/problem/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

 

 

문제풀이

다이나믹프로그래밍

최장 증가 수열(Longest Increasing Subsequence), LIS

dy에는 증가수열의 최대길이를 저장한다. 

 

1. i가 2부터 n+1 까지 반복

2. j는 i-1인 i의 바로 직전부터 0까지 -1씩 감소하면서

  - 현재 값인 arr[i]가 앞쪽에 있는 값인 arr[j]보다 큰 경우를 유지하면서

  - arr[j]가 끝일때 증가수열의 최대 길이 dy[j]가 현재 알고있는 증가수열의 최대길이 max보다 크다면

  - 현재 알고있는 증가수열의 최대 길이를 dy[j]로 갱신

3. dy[j]에서 새롭게 찾은 최대 증가수열의 길이 max에 본인 arr[j]을 더한 길이이므로 +1 해서 dy[j]에 저장

  -  

 

import sys
sys.stdin = open("backjoon_solution1.txt", "r")

n = int(input())
data_list = list(map(int, input().split()))
data_list.insert(0, 0)          #1부터 시작하기 위해서 맨 앞에 0 삽입
dy = [0] * (n + 1)
dy[1] = 1                       #인덱스 1에는 앞에 붙일 숫자 없음


def solutuon(n) :
    result_max = 0

    if n == 1 :
        return 1

    for i in range(2, n+1) :
        max_len = 0

        #i-1부터 0까지 data_list[i]값 보다 작으면서 최대 길이가 긴 경우
        #그 긴 길이에 +1 해서 증가 수열을 구함
        for j in range(i-1, 0, -1):
            if data_list[j] < data_list[i] and dy[j] > max_len :        #[i]보다 [j]는 무조건 작은 수
                max_len = dy[j]                                         #최대 길이값 찾음
        dy[i] = max_len + 1                                             #i-1번째부터 최대 길이 찾은 값으로부터 +1 한다

        #만들어둔 dy값을 이용해서 제일 긴 증가수열 찾음
        if dy[i] > result_max : 
            result_max = dy[i]
    return result_max 

print(solutuon(n))