[백준/파이썬] 14002번 가장 긴 증가하는 부분 수열 4

-Code

n = int(input())
nums = list(map(int, input().split()))
dp = [1] * n

for i in range(n):
    for j in range(i):
        if nums[i] > nums[j]:
            dp[i] = max(dp[i], dp[j] + 1)

l = max(dp)
print(l)
result = []
for i in range(n - 1, -1, -1):
    if dp[i] == l:
        l -= 1
        result.append(nums[i])
print(*reversed(result))

 

1) 처음 코드

n = int(input())
nums = list(map(int, input().split()))
result = []
for i in range(n):
    temp = []
    for j in range(i):
        if nums[i] > nums[j]:
            if nums[j] not in temp:
                temp.append(nums[j])
    temp.append(nums[i])
    if len(result) < len(temp):
        result = temp
print(*result)

처음에는 위와 같이 짜서 입출력은 맞았으나 틀려서 다른 방법을 찾아봤습니다.

 

2) 두 번째 코드

n = int(input())
nums = list(map(int, input().split()))
result = [1]

for i in range(n):
    temp = [nums[i]]
    for j in range(i + 1, n):
        if temp[-1] < nums[j]:
            temp.append(nums[j])
    if len(result) < len(temp):
        result = temp
print(len(result))
print(*result)

두 번째로 짠 코드는 게시판의 반례들을 여러 개 넣어도 값이 맞게 나와서 제출했으나 틀려서 결국 찾아보니 최장 증가수열 알고리즘을 dp로 받고 역순으로 검사하여 수를 저장하는 방식이어서 원래 식에서 조금 바꿔보면 해결이 되는데 못한 것이 아쉬웠고 다른 두 코드의 문제점을 찾지 못해서 아쉬웠습니다.