★DP Upper-Intermediate I - 15 Solved★

★ 2579 계단 오르기 ★

 

# dp 1차원 배열

import sys
input=sys.stdin.readline

N=int(input())
S=[0]

for _ in range(N):S.append(int(input()))

if N==1:print(S[1])
elif N==2:print(S[1]+S[2])
elif N==3:print(S[3]+max(S[1],S[2]))
else:
    dp=[0]*(N+1)

    dp[1]=S[1]
    dp[2]=S[1]+S[2]
    dp[3]=S[3]+max(dp[1],S[2])
    for i in range(4,N+1):
        dp[i]=S[i]+max(dp[i-2],dp[i-3]+S[i-1])
    print(dp[-1])

 

 

🤡 한번에 한 계단, 두 계단을 올라갈 수 있지만, 여기서 중요하게 고려해야 하는 조건은 연속해서 세번 이상 한 계단을 올라갈 수 없다는 점. 따라서 a(n)을 n번째 계단까지 오르는 최고 점수라고 했을 때, 단순히 a(n-1)+a(n-2)라고 점화식을 만들어서는 안된다. n번째 계단을 S(n)이라고 하면, S(n-2)에서 한 번에 두 계단 올라가 S(n)에 도달하는 a(n-2)는 바로 더하기 가능 (아래 빨간색). 하지만 a(n-1)의 경우, S(n-1)에서 한 번에 한 계단으로 S(n)으로 올라가려면 S(n-2)를 거치지 않고 반드시 S(n-3)을 거쳐야 한다. 따라서 a(n-3) 점수에서 S(n-1)을 거치는, a(n-3) + S(n-1)로 정리될 수 있음 (아래 파란색). 점화식 정리하면 a(n) = S(n) + max(a(n-2), a(n-3)+S(n-1))

 

---

# dp 2차원 배열

import sys
input=sys.stdin.readline

N=int(input())
S=[0]
D=[[0,0,0] for _ in range(N+1)]
for _ in range(N):S.append(int(input()))

#initialization
D[1][1] = S[1]
D[1][2] = 0

if N>=2:
    D[2][1] = S[2]
    D[2][2] = S[1]+S[2]

for k in range(3,N+1):
    D[k][1] = max(D[k-2][1],D[k-2][2])+S[k]
    D[k][2] = D[k-1][1]+S[k]

print(max(D[N]))

 

🤡 현재 위치 계단을 오르는 경우는 아래 계단을 거치지 않고 올라오는 경우 + 아래 계단을 거치고 올라오는 경우 2가지 케이스 존재. 이를 각각 D[x][1]과 D[x][2]로 나누어 누적으로 dp 형식으로 더해나간 뒤, 최종적으로 max(D[N]) 연산하는 방법도 존재. D[x][1]은 아래계단을 거치지 않고 올라오는 경우라고 한다면, 아래에서 두번째 계단은 반드시 거쳐야 함. 따라서 D[x-2]의 최댓값 + 현재 계단 S[x]가 정답 / D[x][2]는 아래계단을 거치는 경우이므로 바로 max(D[x-1]) + S[k]라고 생각할 수 있으나, D[x-1][2]는 아래에서 두번째 계단을 거치고 올라온 경우이므로 D[x-1][1]만 고려. 따라서 D[x-1][1] + S[x]가 정답. 

 

---

★ 1932 정수 삼각형 ★

 

import sys
input=sys.stdin.readline

n=int(input())
l=[]

for _ in range(n):l.append(list(map(int,input().split())))

for i in range(1,n):
    l[i][0]+=l[i-1][0]
    for k in range(1,i):l[i][k]+=max(l[i-1][k-1],l[i-1][k]) #dp
    l[i][i]+=l[i-1][i-1]

print(max(l[-1]))

 

🤡 정수 삼각형 문제는 최대 합의 경로 수의 합을 구하는 문제로, 각 층별로 위의 층까지 구한 누적합에서 각 수별로 모두 더해진 수들의 최댓값을 구하는, 전형적인 dp 문제 dp-table 2차원 배열을 만들고, 각 층 기준 맨 첫번째와 맨 끝의 원소는 해당 위치의 수 + 바로 위 층의 수이고, 그 가운데 수들은 위 두 수 중 최댓값에 해당 위치의 수를 더한 결과 l[i][k] = max(l[i-1][k-1], l[i-1][k]) + l[i][k] dp로 쭉 update되면서, 맨 마지막 층의 최댓값이 정답. 추가로 메모리 효율적 사용을 위해 큰 수가 입력될 경우를 대비해, 별도의 dp-table 생성 없이 기존 list에 update 되는 방식으로 푸는게 더 효율적! 

---

★ 1912 연속합 ★ - Kadane's Algorithm

 

import sys
input=sys.stdin.readline
n=int(input())
l=list(map(int,input().split()))
for i in range(1,n):
    l[i]=max(l[i],l[i]+l[i-1])
print(max(l))

 

🤡 주어진 수열의 부분 연속합 최대를 구하는 문제. dp[n]은 ①n원소 자체 ②n원소 + 앞의 dp[n-1] 두 가지 중 최대 합이라는 점화식 사용 dp[n] = max(dp[n-1], L[n]+dp[n-1]) Kadane's Algorithm으로 주어진 배열의 일부 배열 최대합을 구하는 알고리즘이다. (Kadane's Algorithm 포스팅 참조)

---

★ 15645 내려가기 2 ★

 

- 풀이 1 -

import sys
input=sys.stdin.readline

N=int(input())
l=[]
for _ in range(N):
    a,b,c=map(int,input().split())
    l.append([a,b,c])

#find max
dp_max=[l[0]]

for i in range(N-1):
    a,b,c=dp_max[i][0],dp_max[i][1],dp_max[i][2]
    dp_max.append([l[i+1][0]+max(a,b), l[i+1][1]+max(a,b,c), l[i+1][2]+max(b,c)])

#find min
dp_min=[l[0]]

for i in range(N-1):
    a,b,c=dp_min[i][0],dp_min[i][1],dp_min[i][2]
    dp_min.append([l[i+1][0]+min(a,b), l[i+1][1]+min(a,b,c), l[i+1][2]+min(b,c)])

print(max(dp_max[-1]),min(dp_min[-1]))

 

- 풀이 2 -

import sys
input=sys.stdin.readline

N=int(input())
l = list(map(int,input().split()))
dp_max = l
dp_min = l

for i in range(N-1):
    a,b,c=map(int,input().split())
    dp_max=[a+max(dp_max[0],dp_max[1]), b+max(dp_max), c+max(dp_max[1],dp_max[2])]
    dp_min=[a+min(dp_min[0],dp_min[1]), b+min(dp_min), c+min(dp_min[1],dp_min[2])]

print(max(dp_max),min(dp_min))

 

🤡 동일 dp 풀이여도, 주어진 dp-table을 기존 원소 자리에 update하며 메모리를 절약하는 풀이 2 방법이 있다. dp 문제를 풀 때, 기존 dp-table 값들이 최종 답을 구하는 과정에 연관되지 않는다면, 그 자리를 바꾸어가며 update하는 방식으로 풀이 시간을 훨씬 단축할 수 있음. 세 개의 수 각각 위의 수에서 내려오는 여러 경로 중, 최대 또는 최소를 각각 판별해 dp-table 원래값에 계속 update

---

★ 17626 Four Squares ★

 

<1> BF

n=int(input())
end=int(n**(1/2))
if n**(1/2)==end:print(1)
else:
    flag=0
    #check if ans is 2
    for i in range(end,0,-1):
        part=(n-i**2)
        part_root=part**(1/2)
        if part_root==int(part_root):
            flag+=1
            print(2)
            break
    if flag==0:
        #check if ans is 3
        for i in range(end,0,-1):
            part=(n-i**2)
            endp=int(part**(1/2))
            for j in range(endp,0,-1):
                partp=(part-j**2)
                partp_root=partp**(1/2)
                if partp_root==int(partp_root):
                    flag+=1
                    print(3)
                    break
            if flag==1:break
    if flag==0:print(4)

 

<2> DP

n=int(input())
dp=[0]*(n+1)
end = int((n-1)**(1/2))

num_squares = int(n**(1/2))

for i in range(1,num_squares+1):
    dp[i**2]=1

for i in range(1,n):
    for j in range(1,end+1):
        if ((i+j**2)<=n):
            if dp[i+j**2] != 0:
                dp[i+j**2] = min(dp[i+j**2],dp[i]+1)
            else: dp[i+j**2] = dp[i]+1

print(dp[-1])

 

n=int(input())
dp=[0,1]

for i in range(2,n+1):
    m_v,j=5,1
    
    while (j**2)<=i:
        m_v=min(m_v,dp[i-j**2])
        j+=1
    dp.append(m_v+1)
print(dp[n])

 

🤡 모든 자연수는 4개 이하의 제곱수들의 합으로 표현할 수 있는 라그랑주의 이론 문제. 라그랑주의 이론을 안 상태에서 낼 수 있는 풀이이다. 먼저 제곱수인지 확인, 그 다음 2개의 제곱수로 이루어졌는지, 아니면 3개, 그것도 아니라면 4개로 BF 방식으로 일일이 확인. BF는 아래 1부터 차례대로 제곱수를 더하면서 해당 dp-table에 값이 있다면, 이 중 최솟값으로 update, 값이 없다면(0이라면) 출발점에서 1을 더한 값을 넣는 dp-table update 방식. DP는 반대로 1부터 차례대로 살펴보되, 여러 제곱수를 빼면서, 제곱수 뺀 결과의 해당 dp-table 값 중 최솟값에 1을 더한 값을 넣은 dp-table update 방식

 

∴ BF 방식이 월등히 빨랐으며, DP는 일일이 모든 원소를 확인하므로 시간이 많이 걸림

---

★ 1699 제곱수의 합 ★

 

🤡 위 17626번 문제와 똑같은 문제 - 라그랑주의 제곱수 이론 -

---

★ 1309 동물원 ★

 

n = int(input())

dp = [0] * 100001
dp[1] = 3
dp[2] = 7

for i in range(3, n+1):
    dp[i] = (2 * dp[i - 1] + dp[i - 2]) % 9901

print(dp[n])

 

🤡 총 3가지의 경우로 나누어 생각해야 한다.

① 바로 윗 줄에 사자가 한 마리도 없을 때 a(n-1)

② 바로 윗 줄에 왼쪽에만 사자가 한 마리 있을 때 b(n-1)

③ 바로 윗 줄에 오른쪽에만 사자가 한 마리 있을 때 c(n-1)

→ 점화식 x(n-1) = a(n-1) + b(n-1) + c(n-1). n번째 줄에서 각각의 a(n), b(n), c(n)을 구하면

 

① a(n) = a(n-1) + b(n-1) + c(n-1)

→ n번째 줄에 사자가 한 마리도 없다면 윗 줄까지의 모든 세 가지 경우의 수를 합한 결과

② b(n) = a(n-1) + c(n-1)

→ n번째 줄의 왼쪽에만 사자가 있다면, 윗 줄에 사자가 없는 경우의 수 + 윗 줄에 사자가 오른쪽에만 있는 경우의 수

③ c(n) = a(n-1) + b(n-1)

→ n번째 줄의 오른쪽에만 사자가 있다면, 윗 줄에 사자가 없는 경우의 수 + 윗 줄에 사자가 왼쪽에만 있는 경우의 수

 

※ 이 때 a(n-1)은 위 점화식에 의해 a(n-2) + b(n-2) + c(n-2) = x(n-2) (n≥3)이므로 x(n) = a(n) + b(n) + c(n) = (a(n-1) + b(n-1) + c(n-1) + (a(n-1) + c(n-1)) + (a(n-1)+b(n-1)) = x(n-1) + a(n-1) + (a(n-1) + b(n-1) + c(n-1)) = x(n-1) + a(n-1) + x(n-1) = 2x(n-1) + x(n-2)

 

※  최종 점화식 한 줄. 여러 경우의 수를 쪼개 각각의 점화식을 구한 뒤, 합친 점화식을 구한다. 9901로 나눈 나머지를 원하므로, 매 번 연산을 진행할 때마다 업데이트 되는 모든 수를 9901로 나누면서 계속 진행

---

★ 9465 스티커 ★

 

import sys
input=sys.stdin.readline

T=int(input())
for _ in range(T):
    n=int(input())
    sticker=[[0,0] for _ in range(n)]
    x,y=list(map(int,input().split())),list(map(int,input().split()))
    for i in range(n):
        sticker[i][0], sticker[i][1] = x[i], y[i]
    
    dp=[[0,0,0] for _ in range(n)]
    
    dp[0] = [0,sticker[0][0],sticker[0][1]]

    for i in range(1,n):
        dp[i][0] = max(dp[i-1][1],dp[i-1][2])
        dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + sticker[i][0]
        dp[i][2] = max(dp[i-1][0],dp[i-1][1]) + sticker[i][1]

    print(max(dp[-1]))

 

🤡 dp 2차원 배열: dp[i][0]은 i번째 자리에 아무 우편이 배치되지 않았을 때의 최댓값 / dp[i][1]은 위의 우편이 배치되었을 때의 최댓값 / dp[i][2]는 아래 우편이 배치되었을 때의 최댓값 / 최종 결과는 위 세가지 경우 중 최댓값

---

★ 1149 RGB 거리 ★

 

import sys
input=sys.stdin.readline

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

for _ in range(N):
    colors.append(list(map(int,input().split())))

#dp-initialization
dp=[[0,0,0] for _ in range(N)]
dp = colors

for i in range(1,N):
    dp[i][0] = dp[i][0] + min(dp[i-1][1],dp[i-1][2])
    dp[i][1] = dp[i][1] + min(dp[i-1][0],dp[i-1][2])
    dp[i][2] = dp[i][2] + min(dp[i-1][0],dp[i-1][1])

print(min(dp[-1]))

 

🤡 문제를 요약하자면, RGB를 색칠할 때 이웃한 node끼리 동일한 색으로만 칠하지 않으면 된다. dp를 생각할 때 sub-problems로 나눌 수 있는 지의 유무 + 그리고 여러 개의 sub-problems의 합집합이 전체 집합을 차지하는 지의 유무를 생각하면 된다. dp-table에서 현재 채우는 열 기준 위의 열이 R을 골랐을 때 + G를 골랐을 때 + B를 골랐을 때의 총 3가지 sub-problem으로 만들 수 있으며, 이 3개의 sub-problem의 합집합은 전체 problem으로 형성. 최종 update된 마지막 열의 최솟값이 곧 정답

라텍스 문법(예비용) 

$$C(N) = \begin{Bmatrix}
C(N)[0] + min(C(N-1)[1],C(N-1)[2])\\
C(N)[1] + min(C(N-1)[0],C(N-1)[2])) \\
C(N)[2] + min(C(N-1)[0],C(N-1)[1]))
\end{Bmatrix}$$

---

★ 2156 포도주 시식 ★

 

import sys
input=sys.stdin.readline
n=int(input())
gs=[]
for _ in range(n):gs.append(int(input()))

if n==1:print(gs[0])
elif n==2:print(gs[0]+gs[1])
else:
    dp=[[0,0,0,0] for _ in range(n-1)]
    dp[0]=[0,gs[1],gs[0],gs[0]+gs[1]]
    for x in range(1,n-1):
        dp[x][0]=dp[x-1][2]
        dp[x][1]=max(dp[x-1][0],dp[x-1][2])+gs[x+1]
        dp[x][2]=max(dp[x-1][1],dp[x-1][3])
        dp[x][3]=dp[x-1][1]+gs[x+1]
    print(max(dp[-1]))

 

🤡 포도주 마시는 유형은 이전 두 개의 포도주를 마신 경우가 OO, OX, XO, XX인 경우로 나눌 수 있다. (n 2 이하인 경우 제외). dp를 4가지 경우로 나누고, 그 다음 케이스에 O와 X를 나누어 다시 OO, OX, XO, XX인 경우로 나눈다.

 

(1) XX는 XXO / XXX 모두 가능하나 XXX는 포도주를 최대로 마신다는 조건에서 제외

(2) XO는 XOO / XOX 모두 가능

(3) OX는 OXO / OXX 모두 가능

(4) OO는 OOX만 가능

 

즉, XX는 앞선 (3) / XO는 앞선 (1)과 (3)의 최댓값 + 해당 위치 포도주 / OX는 앞선 (2)와 (4)의 최댓값 / XX는 앞선 (2) + 해당 위치 포도주

마지막 dp 4가지 경우 중 최댓값 출력

---

★ 9184 신나는 함수 실행 ★

import sys
input=sys.stdin.readline

dp=[[[1]*21 for _ in range(21)] for _ in range(21)]

for i in range(1,21):
    for j in range(1,21):
        for k in range(1,21):
            if i < j < k:
                dp[i][j][k] = dp[i][j][k-1] + dp[i][j-1][k-1] - dp[i][j-1][k]
            else:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k] + dp[i-1][j][k-1] - dp[i-1][j-1][k-1]

while 1:
    a,b,c=map(int,input().split())
    if (a,b,c) == (-1,-1,-1):
        break
    if a<=0 or b<=0 or c<=0:
        print(f'w({a}, {b}, {c}) = 1')
    else:
        if a > 20 or b > 20 or c > 20:
            print(f'w({a}, {b}, {c}) = {dp[20][20][20]}')
        else:
            print(f'w({a}, {b}, {c}) = {dp[a][b][c]}')

 

🤡 3차원 dp를 활용하는 문제. 위 주어진 점화식 대로 각각 구한다. 시간 초과의 재귀 대신 왜 DP 기법을 활용해야 하는 지 알려주는 문제. 다만 변수가 3개이므로 3차원 list를 활용해야 한다는 점만 주의

---

★ 11053 가장 긴 증가하는 부분 수열 ★

 

import sys
input=sys.stdin.readline

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

dp=[1]*N

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

 

🍝 전형적인 LIS 알고리즘. dp-table 1 initialization

---

★ 11722 가장 긴 감소하는 부분 수열 ★

 

🍝  LIS에서 부등호만 바꾸면 Longest Decreasing Subsequence 알고리즘 변신

import sys
input=sys.stdin.readline

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

dp=[1]*N

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

print(max(dp))

---

★ 11055 가장 큰 증가하는 부분 수열 ★

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

dp=A[::]

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

 

🍝 LIS 변형 문제. 길이가 아니라 Subsequence sum의 최댓값을 구하는 문제이므로 max(dp[x], dp[y]+1)이 아닌, max(dp[x], dp[y]+A[x])로 dp[y]까지의 최대합 + 현재 위치의 원소 합 결과를 dp update.

 

🍝  추가로 주의할 부분.dp=A라 하면 dp update 시 A도 같은 메모리 주소를 공유하기에 update 된다. dp = A[::]로 복제본을 만들어주기

---

★ 18353 병사 배치하기 ★

 

import sys
input=sys.stdin.readline

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

dp=[1]*n

for x in range(1,n):
    for y in range(x):
        if s[x]<s[y]:
            dp[x]=max(dp[x],dp[y]+1)
print(n-max(dp))

 

🍝 Longest Decreasing Subsequence의 길이 제외 나머지 병사 인원수 출력

---