DHistory
[Baekjoon] DP - 11053 가장 긴 증가하는 부분 수열 (오답노트) 본문
문제
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
풀이
import sys
n = int(sys.stdin.readline().rstrip())
numbers = [0] + list(map(int, sys.stdin.readline().rstrip().split()))[:n]
def solution(a):
d = [1] * (len(a))
for i in range(2, len(numbers)):
for j in range(1, i):
# 현재 숫자보다 작은 부분 수열 중 가장 길이가 긴 부분 수열
if a[i] > a[j] and d[i] < d[j] + 1:
d[i] = d[j] + 1
return max(d)
print(solution(numbers))
채점 결과
'Computer Science > Algorithm' 카테고리의 다른 글
| [Baekjoon] DP - 11055 가장 큰 증가하는 부분 수열 (0) | 2023.09.25 |
|---|---|
| [Baekjoon] DP - 1912 연속합 (0) | 2023.09.25 |
| [Baekjoon] DP - 1904 01타일 (0) | 2023.09.20 |
| [Baekjoon] DP - 2193 이친수 (0) | 2023.09.20 |
| [Baekjoon] DP - 9461 파도반 수열 (0) | 2023.09.19 |