세상을 더 좋게

[백준] 11053 '가장 긴 증가하는 부분 수열' 파이썬(python) 본문

Algorithm/DP

[백준] 11053 '가장 긴 증가하는 부분 수열' 파이썬(python)

나는SOU 2021. 12. 4. 00:00

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

N = int(input())

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

dp = [1] * N

for i in range(N):
    for j in range(i):
        if A[j] < A[i]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

Point

  • dp테이블을 이용해 해결하는 DP문제
  • dp테이블 생성해놓고 비교하여 갯수를 업시켜가며 마지막에 최대인 횟수 출력

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

[백준] 1699 '제곱수의 합' 파이썬(python)  (0) 2021.12.08
[백준] 1912 '연속합' 파이썬(python)  (0) 2021.12.07
[백준] 2193 '이친수' 파이썬(python)  (0) 2021.12.04
[백준] 14002 '가장 긴 증가하는 부분 수열 4' 파이썬(python)  (0) 2021.12.04
[백준] 10844 '쉬운 계단 수' 파이썬(python)  (0) 2021.12.04
'Algorithm/DP' Related Articles more