[백준][DP] 가장 긴 감소하는 부분 수열

가장 긴 감소하는 부분 수열

 

• 내 풀이
  • 하나의 num을 확인할 때마다 이전값들을 맨 뒤에서부터 돌면서
    • num보다 큰 값들이 있으면 그 중에서 result 값이 가장 max 인 값을 찾아 업데이트 해준다
    • 값이 같으면 똑같이 복사
  • num 이 가장 큰 경우에는 처음 초기화된 대로 1 부터 시작

 

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

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

for i, num in enumerate(numbers):
    for j in range(i-1, -1, -1):
        if numbers[j] > num:
            result[i] = max(result[i], result[j]+1)
        elif numbers[j] == num:
            result[i] = max(result[i], result[j])

print(max(result))

 

 

• 다른 사람 풀이

n = int(input())
nums = list(map(int, input().split()))
dp = [1 for i in range(n)]
for i in range(n):
    for j in range(i):
        if nums[j] > nums[i]:
            dp[i] = max(dp[i],dp[j]+1)
print(max(dp))