09009

[백준 11053번] 가장 긴 증가하는 부분 수열 본문

Algorithm/DP
[백준 11053번] 가장 긴 증가하는 부분 수열
09009

문제 보기

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

 

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

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

www.acmicpc.net

 

문제 해결

반복문을 원소 하나씩 돌리면서 확인해야한다.

 

 

 

소스 코드

import sys
input = sys.stdin.readline

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

dp = [1] * n

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))

 

'Algorithm > DP' 카테고리의 다른 글

[프로그래머스 lv2] 가장 큰 정사각형 찾기  (0) 2023.10.15
[백준 1699번] 제곱수의 합  (0) 2023.10.03
[백준 2156번] 포도주 시식  (0) 2023.09.06
'Algorithm/DP' Related Articles more
Comments