★DP Advanced I - 4 Solved★

★ 2591 숫자카드 ★

 

n=input()
l=len(n)

if l==1:print(1)
else:
    dp=[0]*l

    #dp-table initialization - dp[0], dp[1]

    dp[0]=1

    front_two=int(n[:2])
    if front_two <=34 and front_two not in [10,20,30]:dp[1]=2
    else:dp[1]=1

    #update dp-table - dp[2]~
    for i in range(2,l):
        if n[i] !='0': #last number is not 0
            dp[i]=dp[i-1]
            if 10 <= int(n[i-1:i+1]) <= 34:
                dp[i]+=dp[i-2]
        else: #last number is 0
            if int(n[i-1])>=4:
                dp[i]=0
            else:
                dp[i]=dp[i-2]
                
print(dp[-1])

 

👄 dp-table을 전형적인 dp 유형 답게 update하는 유형이나, 맨 마지막 숫자가 0일 경우의 예외를 처리하는 dp 유형!

 

👄

① 길이가 1인 경우 - 숫자 1개로 이루어진 카드 1개 - dp[0] = 1

 

② 길이가 2인 경우

(1) 앞의 두 자리 숫자가 34이하이되, 10, 20, 30이 아닌 경우 숫자 1개로 이루어진 카드 2개 & 두 자리 숫자 카드 1개 - dp[1] = 2

(2) 앞의 두 자리 숫자가 위의 케이스가 아니라면 한 자리 숫자 카드 2개 경우 단 1가지 경우 - dp[1] = 1

 

③ 길이가 3이상인 경우

 

(1) 맨 마지막 숫자가 0이 아닌 경우

→ 맨 마지막 두 숫자가 10이상 34이하인 경우, 마지막 숫자가 1개의 카드로 오는 경우 + 마지막 두 개의 숫자가 1개의 카드로 오는 경우

 

dp[i] = dp[i-1] + dp[i-2]

 

→ 위 범위에 해당되지 않는 마지막 두 수라면, 마지막 숫자가 1개의 카드로 오는 경우만 적용

 

dp[i] = dp[i-1]

 

(2) 맨 마지막 숫자가 0인 경우

→ 맨 마지막의 앞자리 숫자가 4이상이면, 마지막 두 자리 숫자(40, 50, 60, 70, 80, 90)은 숫자카드를 만들 수 없으므로

 

dp[i] = 0

 

→ 맨 마지막의 앞자리 숫자가 3이하라면, 마지막 두 자리 숫자(10, 20, 30)은 반드시 한 개의 카드에 있어야 하므로, 두 계단 앞으로 뛴 $dp[i-2]$의 경우의 수 그 자체로 값이 업데이트 된다.

 

dp[i] = dp[i-2]

 

👄 dp-table을 만들되, 문제의 특성 상 4가지의 경우로 나누어 update해줘야 하고, initialization도 경우를 나누어서 해줘야 하는, 분기가 많은 dp 유형

---

★ 14002 가장 긴 증가하는 부분 수열 4 ★

 

import sys
input=sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

dp=[[1,[A[i]]] for i in range(N)]

for x in range(1,N):
    for y in range(x):
        if A[y]<A[x]:
            if (dp[y][0] + 1) > dp[x][0]:
                dp[x][0] = dp[y][0]+1
                dp[x][1] = dp[y][1] + [A[x]]

print(max(dp)[0])
print(*max(dp)[1])

 

🍝 LIS의 길이와 LIS의 수열 내용까지 출력하는 LIS 응용 문제. dp에 LIS 길이 뿐 아니라 LIS path를 두번째 list 원소로 저장한다. 현재 dp[x][0]에 저장된 길이보다 반복문으로 도는 dp[y][0] + 1이 더 클 경우에만 dp[x][0]과 dp[x][1] update. dp에 길이와 path까지 도는 문제

---

★ 2565 전깃줄 ★

 

import sys
input=sys.stdin.readline

N=int(input())
elec=[]

for _ in range(N):
    a,b=map(int,input().split())
    elec.append((a,b))

elec=sorted(elec, key=lambda x: (x[0]))

dp=[1]*N

for x in range(1,N):
    for y in range(x):
        if elec[x][1] > elec[y][1]:
            dp[x]=max(dp[x],dp[y]+1)
print(N-max(dp))

 

🍝 A 전깃줄과 B 전깃줄이 겹치지 않게 하려면 A 전깃줄 오름차순으로 정렬 시, B 전깃줄이 동일하게 오름차순으로 되어야 한다. 겹치지 않게 하는 전깃줄의 최대 개수는 B 전깃줄의 LIS length. A 전깃줄 + B 전깃줄 2개의 정보 들어간 list를 A 기준 sorting한 뒤 B 전깃줄의 LIS dp 진행

---

★ 11054 가장 긴 바이토닉 부분 수열 ★

import sys
input=sys.stdin.readline

N=int(input())

increase=list(map(int,input().split()))
decrease=increase[::-1]

dpi=[1]*N
dpd=[1]*N

for x in range(1,N):
    for y in range(0,x):
        if increase[y] < increase[x]:
            dpi[x] = max(dpi[x],dpi[y]+1)


for x in range(1,N):
    for y in range(0,x):
        if decrease[y] < decrease[x]:
            dpd[x] = max(dpd[x],dpd[y]+1)
dpd=dpd[::-1]

ans=0
for i in range(N):
    ans=max(ans,dpi[i]+dpd[i]-1)
print(ans)

 

🍝 아래 예제를 보면

1 5 2 1 4 3 4 5 2 1

: 각 원소마다 왼쪽에서 시작하는 LIS와 오른쪽에서 시작하는 LIS의 길이를 구하면 된다. 총 2개의 양 방향에의 LIS가 저장된 dpi, dpd의 합 - 1이 각 원소를 기점으로 하는 바이토닉 부분 수열의 길이. 그 중 최댓값은 당연히 가장 '긴' 바이토닉 부분 수열의 길이가 된다.

---