[Python] 동적 프로그래밍 문제 풀이 정리(1)

https://www.acmicpc.net/problem/9095

# 내 풀이
import sys
input = sys.stdin.readline

T=int(input())
D = [0]*11
D[1] = 1
D[2] = 2
D[3] = 4
for i in range(4, 11):
        D[i] = D[i-1]+D[i-2]+D[i-3]
# print(D)
# [0, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274]

for _ in range(T):
    n = int(input())
    
    print(D[n])

• D[n] = 1,2,3으로 n을 만들 수 있는 경우의 수라고 가정하고, 4까지 직접 구해보니 직관적으로 점화식이 나왔다.
• D[i] =D[i-1]+D[i-2]+D[i-3]
• 늘 직관적으로 찾을 수는 없으니 원리를 찾아보았다.
  • 우리가 1,2,3만 사용할 수 있으니, n을 만들기 위해서는 (n-1) or (n-2) or (n-2)에서 각각 1,2,3을 더해주는 경우의 수만 나오는 것이다. 
• n이 11까지만 가능해서 미리 점화식을 다 구해줌.

 

https://www.acmicpc.net/problem/1003

# 첫 풀이
import sys
input = sys.stdin.readline

num0 = 0
num1 = 0

def fibonacci(n):
    global num0, num1
    if n==0:
        # print(0)
        num0+=1
        return 0
    elif n==1:
        # print(1)
        num1+=1
        return 1
    else:
        return fibonacci(n-1)+fibonacci(n-2)
    
T = int(input())
for _ in range(T):
    num0=0
    num1=0
    n = int(input())
    fibonacci(n)
    print(num0, num1)

• fibonnaci 함수를 직접 구현해서 0과 1의 갯수를 직접 세는 방식. 다만 재귀로 풀면 시간초과가 난다.

# 두번째 풀이
import sys
input = sys.stdin.readline

D = []
D.append((1,0))
D.append((0,1))
D.append((1,1))

for i in range(3, 41):
    num0 = D[i-1][0]+D[i-2][0]
    num1 = D[i-1][1]+D[i-2][1]
    D.append((num0, num1))
    
T = int(input())

for _ in range(T):
    n = int(input())

    print(D[n][0], D[n][1])

• D[n] = fibonnaci(n)을 수행할 때 0의 개수, 1의 개수이다.
• 피보나치의 원리에 따라 점화식을 수행한다.
• 피보나치 수열의 원리를 적용하지만 구현할 필요는 없다. 전형적인 DP문제!

 

https://www.acmicpc.net/problem/11727

# 정답 풀이
import sys
input = sys.stdin.readline

D = [0]*1001
D[1] = 1
D[2] = 3
D[3] = 5 # D[4] = 11
for i in range(4, 1001):
    D[i] = (D[i-1]+2*D[i-2])%10007

print(D[int(input())])

• D[n] = D[n-1] + D[n-2]*2 라는 점화식을 도출할 수 있다.
  • D[n-1] 즉 길이가 1만큼 작은 경우에서 D[n]을 만들기 위해서는 타일 2x1 타일 하나를 추가하는 경우의 수만 존재하므로 그대로 더한다.
  • D[n-2] 즉 길이가 2만큼 작은 경우에서는 1x2 타일 2개 혹은 2x2 타일 1개를 붙이는 경우가 존재하므로 D[n-2]*2 만큼 경우의 수가 추가된다. 2x1 타일 2개를 붙이는 경우는 D[n-1]과 겹치므로 고려하지 않는다.

 

https://www.acmicpc.net/problem/9465

# 정답 풀이
import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T) :
    n = int(input())
    dp = [list(map(int,input().split())) for _ in range(2)]

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

    print(max(dp[0][n-1],dp[1][n-1]))

• 마지막 출력은 두 행 중 최댓값을 출력한다.
• DP 배열을 2중(2차원 배열)로 만들고 전열/전전열까지 고려해야 했따. 실버 1은 어렵당

 

https://www.acmicpc.net/problem/11052

# 내 풀이
import sys
input = sys.stdin.readline

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

D = [0]*(N+1)
for i in range(1, N+1):
    k = i
    j = N
    while k>0:
        D[i] += (j//k)*P[k-1]
        j%=k
        k = j%k
        
print(max(D))

• D 배열에 현재 값을 포함하여 살 수 있는 금액을 저장한다. 동전 문제와 같이 연산을 통해 금액 계산
• 틀림. 안될 것 같긴 함...최댓값이라는 보장이 없다.

# 정답 풀이
n = int(input())
p = list(map(int, input().split()))
p.insert(0,0)
dp = [0 for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1,i+1):
        dp[i] = max(dp[i], p[j] + dp[i-j])
print(dp[n])

• dp[4]의 경우, dp[1]+dp[3]/ dp[2]+dp[2]/ dp[3]+dp[1]/ dp[4] 중 큰 값을 선택하게 된다.
• j값에 따라 각 이전 dp의 조합을 만들어내 최댓값을 비교 후 저장한다. 

 

https://www.acmicpc.net/problem/11057

# 정답 풀이
import sys
input = sys.stdin.readline

n = int(input())
dp = [1] * 10

for i in range(n-1):
    for j in range(1, 10):
        dp[j] += dp[j-1]

print(sum(dp) % 10007)

• n=1일 때는 10이다.
• n=2일 때, 끝자리수가 0,1,2,...,9에 따라 가능한 경우의 수는 1,2,3,...,10이된다.
• n=3일 때도 마찬가지로 끝자리수가 0,1,2,...9에 따라 가능한 경우의 수는 1,3,6...55가 된다.
• N= 자릿수, j= 끝의 수라 할 때 점화식은 D[N][j] = D[N-1] + D[j-1]이 된다. 이전 식을 계속 사용하므로(D[N]을 만들 때 D[N-1]을 이용함) D[j] += dp[j-1]이 도출된다.
• 규칙 찾기 어렵다..

 

 

---

# 회고

 

연습을 많이 해야겠다...

딱 실버 3까지의 수준인듯. 실버 1은 규칙이 한눈에 안보인다ㅜ 손으로 직접 푸는 연습을 하자.