[백준 2024/03/23] 11053번 가장 긴 증가하는 부분 수열

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

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

 

1. 접근 방법

처음에 접근을 잘못했다가 많이 헤맨 문제이다. 

dp를 이용해서 문제를 풀어야 한다. 

이때, dp란? : 최적 부분 구조와 중복되는 부분문제를 가지는 것이다.

중복되는 부분문제는 말그래도 중복되는 문제를 가지는 것이고, 최적 부분 구조는 문제를 해결하기 위한 최적의 방법은 문제를 구성하는 부분 문제들의 최적의 방법으로부터 구성될 수 있다고 하는 것이다.

 

이번 문제는 수열의 크기만큼 dp를 구성해서, 해당 인덱스 위치를 끝으로 하는 LIS의 최대 길이를 저장해 두었다. -> 처음에는 1로 초기화

이후, 2중 for문을 통해, 해당 인덱스의 이전 인덱스에서 현재 인덱스로 이동할 때의 값 비교를 통해서 더 큰 값을 인덱스에 저장해 두었다.

( 값이 증가하는 방식일 때만 비교해 주었다.)

 

 

2. 코드

def lis_length(nums):
    if not nums:
        return 0

    # DP 테이블 초기화
    dp = [1] * len(nums)  # 각 위치를 끝으로 하는 LIS의 길이를 저장. 최소 길이는 1이므로 1로 초기화.

    # 모든 위치에 대해 LIS 계산
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    # DP 테이블에서 최대 값을 찾음
    return max(dp)


height = int(input())
# 입력 예시
nums = list(map(int, input().split()))
print(lis_length(nums))