[dp/백준] 14002번: 14002번: 가장 긴 증가하는 부분 수열4

-문제:https://www.acmicpc.net/problem/14002

 

DP 2차 복습 끝. 몇 문제는 다시 푸니까 잘 풀렸지만, 아직 많은 문제들을 답지 보고 풀어야하는 상태이다. 

다시 봐야할 문제들 위주로 다시 풀어보려고 한다 

 

-정답 풀이: 

윗 부분은 기존 풀이랑 동일하다. 

수열에 해당하는 숫자는 거꾸로 가면서 ans 문자열에 추가해주면 된다 

n=int(input())
data=list(map(int,input().split()))
dp=[0]*n

for i in range(n):
    for j in range(i+1):
        if data[i]>data[j] and dp[i]<dp[j]:
            dp[i]=dp[j]            
    dp[i]+=1
now=max(dp)
ans=''
for i in range(n-1,-1,-1):
    if dp[i]==now:
        ans=str(data[i])+' '+ans
        now-=1
    
print(max(dp))
print(ans)

 

-정답풀이 2:

이렇게 수정하니까 또 정답이다. 시간은 위의 풀이보다 2배 정도 더 걸렸다. 

아무래도 idx를 구하는데 문제가 있었던 것 같다 

n=int(input())
data=list(input().split())
dp=[[""]*n,[0]*n]

for i in range(n):
    for j in range(i+1):
        if int(data[i])>int(data[j]) and dp[1][i]<dp[1][j]:
            dp[0][i]=dp[0][j]
            dp[1][i]=dp[1][j]
    dp[0][i]+=(data[i]+" ")
    dp[1][i]+=1

now=max(dp[1])
idx=dp[1].index(now)
print(now)
print(dp[0][idx])

 

-시도해본 풀이:

부분 수열에 해당하는 숫자들을 따로 저장한 뒤 그거를 불러오는 로직을 생각했는데, 

계속 틀렸다. 아무래도 이 방법은 아닌 것 같다 

n=int(input())
data=list(input().split())
dp=[['']*n,[0]*n]

for i in range(n):
    for j in range(i+1):
        if int(data[i])>int(data[j]) and dp[1][i]<dp[1][j]:
            dp[0][i]=dp[0][j]
            dp[1][i]=dp[1][j]
    dp[0][i]+=(' '+data[i])
    dp[1][i]+=1

for i in range(1,n):
    if len(dp[0][i])>len(dp[0][i-1]):
        idx=i
answer=dp[0][idx]       
print(max(dp[1]))
print(answer[1:])