[DP/백준]11722

zzarbttoo·2021년 8월 27일
0

백준

목록 보기
5/17

백준 DP 11722 파이썬 풀이

아무리 생각해도 뭔지 모르겠어서
다른 블로그를 참고해보니 for문을 두개 중첩해서 하는 것도 가능하더라

def solution(n, param_array):

    count_array = [1 for _ in range(n)]

    for current_index, current_num in enumerate(param_array):
        compare_count_array = []
        for before_index in range(current_index):
            if param_array[before_index] > current_num:
                compare_count_array.append(count_array[before_index])
        if compare_count_array:
            count_array[current_index] += max(compare_count_array)

    return max(count_array)
            


# n = 6
# param_array = [10, 30, 10, 20, 20, 10]


n = int(input())
param_array = list(map(int, input().split()))

print(solution(n, param_array))
  • 이전의 수들을 모두 비교해 현재보다 크기가 큰 수의 count값을 모두 저장한다
  • 이후 저장한 count값 + 1이 현재의 count값이 된다
profile
나는야 누워있는 개발머신

0개의 댓글