BOJ DP문제

링크: https://www.acmicpc.net/problem/14002

수열 A 중에서 a[i-1] < a[i] 가 만족하는 가장 긴 수열을 찾아 길이와 그 리스트를 출력하는 문제다.

접근 1

1. n 크기의 dp 리스트의 각 요소를 1로 초기화 시켜주고(1미만의 길이는 나오지 않음) dp 리스트엔
   길이를 비교하기 위한 카운트를 저장.
2. 수열 A를 순회하며 a[i]의 이전 요소들의 길이를 구하고 a[i]보다 작은 수 중에서
   가장 긴 길이+1을 dp[i]에 저장하고 마지막엔 dp 리스트 중에서 제일 큰 값을 따로 저장해둔다.
3. 가장 긴 길이를 cnt에 저장시켜주고 새로운 리스트 ans를 만들어 dp[i]와 cnt가 같고
   ans[-1]보다 작은 a[i]를 찾아서 하나씩 ans에 추가시켜주고 cnt를 1씩 차감시켜준다.
4. 뒤에서부터 탐색을 끝내면 숫자가 역순으로 돼있어 출력 시에 리스트를 뒤집어 출력시켜준다.

코드 1

import sys

input = sys.stdin.readline

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

dp=list()
dp=[1]

for x in range(1,n):
    tmp = [1]
    for y in range(x):
        if ilist[x] > ilist[y]:
            tmp.append(dp[y]+1)
    
    dp.append(max(tmp))

mx = max(dp)
cnt = mx-1
ans = [ilist[dp.index(mx)]]
for x in range(n-1,-1,-1):
    if cnt == 0:
        break
    if dp[x] == cnt and ans[-1] > ilist[x]:
        ans.append(ilist[x])
        cnt -=1
print(mx)
print(*ans[::-1])

예제 입력과 다른 예제 케이스들을 입력해 봤지만 결과는 오답.

수정1

여러 케이스들을 입력해 봐도 몰라서 다른 사람 코드를 가져와서 랜덤으로 값을 넣어 차이를 확인해 봄.

코드 1이 내가 짠 코드고 코드 2가 구글에서 가져온 코드다.
최대 길이는 같게 나오고 리스트 출력에서 차이가 보이는데 문제에서 최대 길이의 부분 수열 중
아무거나 출력하라 했었는데 테스트 횟수를 늘려도 길이는 똑같은데 출력 순서의 문제인 것 같다.
검색 코드를 참조하여 ans에 저장, 출력하는 방식만 살짝 바꿔봤다

코드2

import sys

input = sys.stdin.readline

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

dp=list()
dp=[1]

for x in range(1,n):
    tmp = [1]
    for y in range(x):
        if ilist[x] > ilist[y]:
            tmp.append(dp[y]+1)
    
    dp.append(max(tmp))

mx = max(dp)
cnt = mx
ans = []
for x in range(n-1,-1,-1):
    if dp[x] == cnt:
        ans.append(ilist[x])
        cnt -=1
print(mx)
print(*ans[::-1])

코드 1의 "ans = [ilist[dp.index(mx)]]" 이 부분에서 제일 큰 차이인 것 같다 코드를 확인하면서
굳이 초기화하고 시작하지 않아도 된다는 걸 알았지만 아무거나 출력하라고 돼있어 다른 문제인 줄 알아서
헷갈렸다