★DP Intermediate I - 20 Solved★

★ 17202 핸드폰 번호 궁합 ★

 

A=list(input())
B=list(input())
l=[]
for i in range(8):l.extend((int(A[i]),int(B[i])))
while len(l)>2:
    L=len(l)
    for j in range(L-1):l[j]=(l[j]+l[j+1])%10
    del l[-1]
print(*l,sep='')

---

★ 16395 파스칼의 삼각형 ★

 

 

n,k=map(int,input().split())
d=[0]*n
d[0]=1
if n==1:print(1)
else:
    for i in range(1,n):
        new=[]
        new.append(1)
        for j in range(i-1):
            new.append(d[i-1][j]+d[i-1][j+1])
        new.append(1)
        d[i]=new
    print(d[n-1][k-1])

 

😻 전형적인 DP 문제 ① 파스칼의 삼각형 층 개수에 맞게 dp list를 만들어 메모리 할당 / ② 각 층 별로 위의 층을 참조해(바로 위 두 원소의 합 결과) 할당된 메모리 공간에 대입 → 2차원 list 완성 ③ 주어진 층의, 주어진 순서의 원소를 2차원 list에서 출력. 위 층의 두 원소를 참조로 아래 층을 만들어나가므로 bottom-up 상향식 dp 유형. dp는 이미 계산된 결과를 참고해 쉽게 다음 결과를 만들어 나가면서, 주어진 메모리 내에서 결과를 채우는 유형. 파스칼의 삼각형은 이항계수를 이용해 공식으로 바로 풀리지만, dp의 정석에 맞게 풀어봄!

---

★ 15489 파스칼 삼각형 ★

 

R,C,W=map(int,input().split())
dp=[]
dp.extend(([1],[1,1]))

for i in range(2,R+W-1):
    l=[]
    l.append(1)
    for j in range(1,i):
        l.append(dp[i-1][j-1]+dp[i-1][j])
    l.append(1)
    dp.append(l)
ans=0
p=1
for k in range(R-1,R+W-1):
    for t in range(C-1,C-1+p):
        ans+=dp[k][t]
    p+=1
print(ans)

 

😻 위 16395 문제대로 파스칼 삼각형을 dp로 완성한 뒤, R번째 C번째 수를 삼각형 위 꼭짓점으로 하고 변이 W인 정삼각형 내부의 모든 수의 합 구하기. 이중 for문으로 ① 먼저 k iterator로 R층부터 R+W-1층까지 합을 구해야 하므로 배열 index 기준 R-1부터 R+W-2까지, 즉 range(R-1,R+W-1) / ② 이제 각 k층에서 C번째부터 층 숫자가 올라가면서 1개, 2개, 3개 더해지므로 p iterator를 따로 설정해 range(C-1, C-1+p), p+=1

---

★ 11726 2xn 타일링 ★

 

n=int(input())
if n==1:print(1)
else:
    dp=[0]*(n+1)
    dp[1]=1
    dp[2]=2
    for i in range(3,n+1):
        dp[i]=dp[i-1]+dp[i-2]
    print(dp[n]%10007)

 

😻 위 문제 dp의 점화식은 fibonacci와 같다. a(n)을 2xn 크기의 직사각형에서 타일을 채우는 개수라고 했을 때, 점화식은 이와 같다. a(n) = a(n-1) + a(n-2) (a(1) = 1, a(2) = 2. 변의 길이가 n-1일 경우 2x1 직사각형을 추가하는 1가지 방법이 있고, 변의 길이가 n-2일 경우, 1x2 직사각형 두개를 가로로 누워서 추가하는 1가지 방법이 있다. 따라서 변의 길이가 각각 n-1, n-2일때의 방법을 더해주기만 하면 된다. dp-table의 첫 스타트가 되기 위한 초기항들을 잘 설정만 주의

 

---

★ 11727 2xn 타일링 2 ★

 

n=int(input())
if n==1:print(1)
else:
    dp=[0]*(n+1)
    dp[1]=1
    dp[2]=3
    for i in range(3,n+1):
        dp[i]=dp[i-1]+2*dp[i-2]
    print(dp[n]%10007)

 

😻 위 11726 dp문제에서 2x2 정사각형이 추가된 문제 위 그림과 같이 a(n-2)는 두 가지 방법으로 2xn 타일을 채울 수 있으므로 해당 항만 2를 곱해 점화식을 완성하면 된다. a(n)을 2xn 크기의 직사각형에서 타일을 채우는 개수라고 했을 때, 점화식은 a(n) = a(n-1) + 2*a(n-2) (a(1) = 1, a(2) = 3). 변의 길이가 n-1일 경우 2x1 직사각형을 추가하는 1가지 방법이 있고, 변의 길이가 n-2일 경우, 1x2 직사각형 두개를 가로로 누워서 추가, 2x2 정사각형 1개를 추가하는 2가지 방법이 있다. 따라서 변의 길이가 각각 n-1, n-2일때의 각 경우의 수를 더해주기만 하면 된다. (역시 11726 위 문제와 마찬가지로 초기항 주의)

---

★ 1463 1로 만들기 ★

 

n=int(input())
dp=[0]*(n+1)
if n==1:print(0)
elif n==2:print(1)
else:
    dp[2],dp[3]=1,1
    for i in range(4,n+1):
        a,b,c=1000001,1000001,1000001
        if i%3==0:
            a=dp[i//3]
        if i%2==0:
            b=dp[i//2]
        c=dp[i-1]
        dp[i]=min(a,b,c)+1
    print(dp[n])

 

🤡 dp-table의 element는 각각 연산을 하는 횟수의 최솟값. dp[n]을 기준으로, dp[n//3], dp[n//2], dp[n-1]에서 각각 3을 곱하고, 2를 곱하고 1을 더하는 1번의 연산 중 최솟값 결과로 dp[n]에 도달 가능. 점화식을 세우면 a(n) = min(a(n//3), a(n//2), a(n-1) + 1)

---

★ 1904 01 타일 ★

 

N=int(input())
if N==1:print(1)
elif N==2:print(2)
else:
    dp=[1,2]
    for _ in range(N-2):
        dp.append((dp[-2]+dp[-1])%15746)
    print(dp[-1]%15746)

 

🤡 피보나치 수열 dp문제. dp[x]인 길이가 x인 2진 수열을 만들 수 있는 모든 경우의 수는 맨 앞에 1이 올 경우 dp[x-1], 그리고 맨 앞에 00이 올 경우 dp[x-2]의 두 가지 상황만 존재하므로 간단하게 dp[x] = dp[x-1] + dp[x-2]

---

★ 9461 파도반 수열 ★

 

for _ in range(int(input())):
    dp=[0,1,1,1,2,2,3,4,5]
    N=int(input())
    if N<=8:print(dp[N])
    else:
        dp.extend([0]*(N-8))
        for i in range(9,N+1):
            dp[i]=dp[i-1]+dp[i-5]
        print(dp[N])

 

😻 N이 9이상일 때 부터 삼각형의 변의 길이는 규칙상 앞의 P값과 5계단 앞의 P값을 더한 결과이다. 점화식을 정리해보면 P(N) = P(N-1) + P(N-5) (N≥9). N이 8이하일 경우 P(N)은 N이 1일 때부터 차례대로 1, 1, 1, 2, 2, 3, 4, 5

---

★ 9095 1, 2, 3 더하기 ★

 

for _ in range(int(input())):
    dp=[0,1,2,4]
    n=int(input())
    if n<=3:print(dp[n])
    else:
        dp.extend([0]*(n-3))
        for i in range(4,n+1):
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
        print(dp[n])

 

😻 n을 1,2,3의 합으로 나타내는 가짓수를 a(n)이라고 한다면, 1을 뺀 수의 가짓수에서 1을 더하는 1가지 경우, 2를 뺀 수의 가짓수에서 2를 더하는 1가지 경우, 3을 뺀 수의 가짓수에서 3을 더하는 1가지 경우로 총 3가지 경로가 존재한다. 여기서 만약 2를 뺀 수의 가짓수에서 2를 더하는 것 뿐만 아니라, 1을 2번 더하는 경우도 고려될 수 있으나, 이는 이미 1을 뺀 수의 가짓수에서 1을 더하는 경로에 카운트되었으므로 배제. 3을 뺀 경우의 수에서도 고려. 점화식을 정리하자면 a(n) = a(n-1) + a(n-2) + a(n-3) (a(1) = 1, a(2) = 2, a(3) = 4)

---

★ 15312 이름 궁합 ★

 

A=list(input())
B=list(input())
l=[]
lines='32123323322122122212111221'
alphas='ABCDEFGHIJKLMNOPQRSTUVWXYZ'
for i in range(len(A)):l.extend((int(lines[alphas.index(A[i])]),int(lines[alphas.index(B[i])])))
while len(l)>2:
    L=len(l)
    for j in range(L-1):l[j]=(l[j]+l[j+1])%10
    del l[-1]
print(*l,sep='')

 

😻 새로 dp-table을 만들기에는 최대 400만까지 list가 늘어나 메모리 초과 가능성이 있으므로, 기존 list에서 bottom-up 방식으로 dp-table을 update해 나가는 방식으로 코드를 짰음. 두 원소를 더한 결과를 앞 원소값과 바꾸면서 계속 update하는 역시 전형적인 dp 문제

---

★ 14495 피보나치 비스무리한 수열 ★

 

#f(n)=f(n-1)+f(n-3)
n=int(input())
if n<=3:print(1)
else:
    dp=[0,1,1,1]
    for i in range(4,n+1):
        dp.append(dp[i-1]+dp[i-3])
    print(dp[n])

 

😻 점화식 a(n) = a(n-3) + a(n-1)

---

★ 13699 점화식 ★

 

n=int(input())
if n==0:print(1)
else:
    dp=[1]*(n+1)
    for i in range(1,n+1):
        term=0
        for j in range(0,i):
            term+=(dp[j]*dp[(i-1-j)])
        dp[i]=term
    print(dp[-1])

 

😻 점화식의 j가 0부터 i-1까지 쭉 돌아야 하므로 bottom-up 반복문이되, 이중 반복문. t(n) = t(0)*(tn-1) + t(1)*t(n-2) + ... + t(n-1)*t(0)

---

★ 2491 수열 ★

 

import sys
input=sys.stdin.readline
N=int(input())
l=list(map(int,input().split()))

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

for i in range(1,N):
    if l[i-1]<=l[i]:
        dpi[i]=(dpi[i-1]+1)
    if l[i-1]>=l[i]:
        dpd[i]=(dpd[i-1]+1)
print(max(dpi+dpd))

 

😻 LIS는 연속성 없이 부분 증가 수열의 길이를 구하는 문제이지만, 해당 문제는 연속해서 같거나 증가하는 / 같거나 감소하는 수열의 길이를 구하는 경우라 바로 점화식 세우면 된다. 연속해서 같거나 증가 / 연속해서 같거나 감소하는 각각의 dp 만들어 진행한다. dpi[i] = dpi[i-1] + 1 (if l[i]≥l[i-1])  / dpd[i] = dpd[i-1] + 1 (if l[i]≤l[i-1]) 두 dp-table 중 최댓값을 구하면 끝!

---

★ 25644 최대 상승 ★

 

import sys
input=sys.stdin.readline
N=int(input())
a=list(map(int,input().split()))
dp=[0]*N
cur_min=a[0]
for i in range(1,N):
    if a[i-1]<cur_min: cur_min=a[i-1]
    dp[i]=(a[i]-cur_min)
print(max(dp))

 

😻 점화식 dp[i]는 a[i]를 사는 경우 얻을 수 있는 최대 이익이라면, greedy에 의해 사고 팔아서 얻을 수 있는 최대 이익은 일단 사는 경우는 a[i]로 정해져 있으므로, 파는 금액이 최소가 되어야 한다. 따라서 dp로 돌면서 앞의 모든 원소들의 파는 금액 최솟값 update.  점화식은 dp[i] = a[i] - min(cur) (min(cur)은 현재 i-1번째 까지의 원소 중 최솟값). dp-table이 완성되면, 이 element 중 최댓값이 얻을 수 있는 금액의 최댓값으로 정답이 된다.

---

★ 25214 크림 파스타 ★

 

import sys
input=sys.stdin.readline
N=int(input())
dp=[0 for _ in range(N)]
As=list(map(int,input().split()))

cur_min=As[0]

for i in range(1,N):
    dp[i]=max(dp[i-1],As[i]-cur_min)
    cur_min=min(cur_min,As[i])
print(*dp)

 

😻 문제의 식을 해석해보면, element를 계속 추가할 때 마다 index가 큰 원소에서 index가 작은 원소를 뺀 값 중 최댓값을 계속 update하는, dp-table을 출력하는 문제. greedy에 의해 해당 차이의 최댓값은, 새로 추가된 원소의 기준에서, 앞에서 주어진 원소 중 최솟값을 뺀 경우이다. dp[i]는 element가 추가되면서 생기는 list내 두 element의 차이 최댓값. dp[i] = max(dp[i-1], As[i] - min(cur)) (As는 원소 list, cur_min은 업데이트 되는 현 최솟값)

---

★ 14494  다이나믹이 뭐예요? ★

 

n,m=map(int,input().split())
dp=[[0]*m for _ in range(n)]
dp[0][0]=1

for i in range(n):
    for j in range(m):
        if i==0: dp[i][j]=1
        elif j==0: dp[i][j]=1
        else:dp[i][j]=(((dp[i-1][j]%1_000_000_007)+(dp[i][j-1]%1_000_000_007)+(dp[i-1][j-1]%1_000_000_007))%1_000_000_007)

print(dp[n-1][m-1])

 

😻 2차원 배열 dp 전형적인 문제. 위 / 아래 / 왼쪽 대각선 각각의 총 세 방향에서 오는 경로의 모든 합으로 업데이트. 점화식은 dp[i][j] = dp[i-1]j] + dp[i][j-1] + dp[i-1][j-1]

---

★ 9655 돌 게임 ★

 

N=int(input()) #~1000
dp=[0]*(1001)
dp[1],dp[2],dp[3]='SK','CY','SK'
if N<=3:
    print(dp[N])
else:
    for i in range(4,N+1):
        if dp[i-1] == 'SK':
            dp[i]='CY'
        else:
            dp[i]='SK'
    print(dp[N])

 

😻 앞 사람이 SK면 CY, 아니면 SK. 앞의 결과에 따라 그 다음 게임의 승자가 바로 정해지는 DP

---

★ 9625 BABBA ★

 

k=int(input())
dp=[[0,0] for _ in range(46)]
a,b=0,0
dp[1]=[0,1]
if k==1:
    print(*[0,1])
else:
    for x in range(2,k+1):
        dp[x][0] = dp[x-1][1] #A
        dp[x][1] = dp[x-1][0] + dp[x-1][1]#B
    print(*dp[k])

 

😻 A는 B로 바뀌고, B는 BA로 바뀌므로 A는 이전 B의 개수 / B는 이전 A의 개수 + B의 개수 

---

★ 9507 Generations of Tribbles ★

 

import sys
input=sys.stdin.readline

dp=[0]*68
dp[0],dp[1]=1,1
dp[2]=2
dp[3]=4
for _ in range(int(input())):
    n=int(input())
    if n<=3:
        print(dp[n])
    else:
        for x in range(4,n+1):
            dp[x] = dp[x-1] + dp[x-2] + dp[x-3] + dp[x-4]
        print(dp[n])

---

★ 15624 피보나치 수 7 ★

n=int(input())
BIG = 1000000007
if n == 0:
    print(0)
elif n == 1:
    print(1)
else:
    x,y=0,1
    for i in range(n):
        x,y=(x+y)%BIG, x%BIG
    print(x)

 

😻 대표적인 피보 DP. x,y에 x+y,x각각 넣으며 두 변수 x,y만으로 DP 업데이트하며 메모리 효율적 사용

---