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 |
블로그의 정보
농담곰담곰이의곰담농
브이담곰