세상을 더 좋게

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

Algorithm/DP

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

나는SOU 2022. 1. 8. 00:00

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

 

11722번: 가장 긴 감소하는 부분 수열

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

www.acmicpc.net

N = int(input())
numbers = list(map(int, input().split()))
dp = [1 for i in range(N)]

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

Point

  • dp테이블을 활용한 DP 문제이다.
  • 두 개의 수열을 이용하여 비교해나가는 문제로서 이전의 수열들 문제와 상당히 비슷하다. 다른 점은 dp테이블에 수열의 갯수를 담은 것

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

[백준] 11054 '가장 긴 바이토닉 부분 수열' 파이썬(python)  (0) 2022.01.11
[백준] 13398 '연속합 2' 파이썬(python)  (0) 2022.01.11
[백준] 11055 '가장 큰 증가 부분 수열' 파이썬(python)  (0) 2022.01.08
[백준] 2156 '포도주 시식' 파이썬(python)  (0) 2021.12.24
[백준] 1932 '정수 삼각형' 파이썬(python)  (0) 2021.12.24
'Algorithm/DP' Related Articles more