백준 11053 <가장 긴 증가하는 부분 수열> Python

JunOnJuly 2023. 11. 4. 21:16

728x90

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

백준 11055 <가장 큰 증가하는 부분 수열>

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열

dev-diary-0717.tistory.com

11055 번 <가장 큰 증가하는 부분 수열> 의 하위호환 문제라고 할 수 있습니다.

def solution(N, data_list):

# DP

memo = [1 for _ in range(N)]

# 첫 부분 작성

memo[0] = 1

# 순서대로 최댓값을 늘리고 거꾸로 탐색하면서 메모 최신화

for idx_now in range(N):

for idx_reverse in range(idx_now, -1, -1):

# 현재 인덱스의 값보다 작은 값이 앞에 존재하면 그 값 + 1 메모, 더 큰 값이 존재하면 업데이트

if data_list[idx_reverse] < data_list[idx_now] and memo[idx_now] <= memo[idx_reverse]:

memo[idx_now] = memo[idx_reverse]+1

return max(memo)

N = int(input())

data_list = list(map(int, input().split()))

print(solution(N, data_list))

728x90