농담곰담곰이의곰담농

11053 가장 긴 증가하는 부분의 수열

by 브이담곰

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

✔ 유형 : DP(LIS)

✔ 문제 풀이: 

 

LIS(Longest Increase Sequence) 의 로직과 비슷하다.

 

DP[i] 를 i 번째 까지 가장 긴 증가하는 부분 수열의 개수라고 정의했을 때.

 

i보다 앞쪽에 있는 원소들과 비교해서 i번째의 수보다 작을 때 개수를 업데이트 한다.

 

정리하자면,

DP[i] : 현재까지 계산된 i위치에서의 LIS의 길이

DP[j] + 1 : j위치까지 LIS에 현재 원소를 추가한 길이

 

그리고 D[i] 는 위의 두 경우의 수 중 최대값으로 업데이트 해주어야한다.

 

따라서, "현재 원소를 이전 LIS 에 추가했을 때 더 긴 LIS가 되는가?"를 조건을 생각해주면 되는것이다.

 

코드

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

DP = [1] * N  # 모든 원소의 최소 길이는 1

for i in range(1, N):
    for j in range(i):
        if arr[i] > arr[j]:
            DP[i] = max(DP[i], DP[j] + 1)

print(max(DP))

 

'Coding Test > Baekjoon' 카테고리의 다른 글

10844 쉬운 계단 수  (0) 2024.08.14
2156 포도주 시식  (0) 2024.08.10
1464 1로 만들기  (0) 2024.08.07
1923 연속합  (0) 2024.08.06
1932 정수 삼각형  (0) 2024.08.05

블로그의 정보

농담곰담곰이의곰담농

브이담곰

활동하기