오답노트 - 가장 긴 바이토닉 부분 수열

LCS를 이용해서 수월하게 풀었다. 다만, 한달 전에 재출했던 풀이 보다 시간이 30%정도 더 걸렸다고 나왔다.

CODE

import sys
read=sys.stdin.readline

n=int(read())
num=list(map(int,read().split()))
num=[0]+num+[0]

#DP각 원소에 해당 숫자까지의 가장 긴 증가하는 부분수열,
#해당 숫자 부터 시작되는 가장 긴 감소하는 부분수열의 길이 저장
dp=list([0,0] for _ in range(n+2))

for i in range(n,0,-1):
    for j in range(n+1,i,-1):
        if dp[j][1]>=dp[i][1] and num[j]<num[i]:
            dp[i][1]=dp[j][1]+1
for i in range(1,n+1):
    for j in range(0,i):
        if dp[j][0]>=dp[i][0] and num[j]<num[i]:
            dp[i][0]=dp[j][0]+1
answer=0
for i in range(1,n+1):
    answer=max(answer,sum(dp[i]))
print(answer-1)


탈출

DP문제인 것 같은데, 1로만들기 같은 문제보다 생각하기가 조금 더 까다로웠다.

CODE

import sys
read=sys.stdin.readline
from collections import deque

n,t,g=map(int,read().split())

dp=list(-1 for _ in range(100_000))
dp[n]=0

point=deque([n])

answer=-1
while point:
    a=point.popleft()
    if a == g:
        answer=dp[a]
        break
    if a ==0 and dp[1]>dp[0]+1:
        dp[1]=dp[0]+1
        point.append(1)
    else:
        if a*2<100_000:
            tmp=str(a*2)
            if tmp[0]=='1': tmp=tmp[1:]
            else:
                tmp=str(int(tmp[0])-1)+tmp[1:]
            tmp=int(tmp)
            if dp[tmp]==-1 and tmp>=0:
                dp[tmp]=dp[a]+1
                point.append(tmp)
        if a+1<100_000:
            if dp[a+1]==-1:
                dp[a+1]=dp[a]+1
                point.append(a+1)

if answer==-1 or answer>t: print("ANG")
else: print(answer)


풀어야 할 문제

  • 스타트 택시
  • 미네랄
  • 회전 초밥
  • 아기 상어
  • 전깃줄 -2
  • 치즈