[백준] DP 관련 문제 모음(Python)

1. 1로 만들기 - 실버3

import sys
input = sys.stdin.readline

n = int(input())
count = 0

dp = [0] * (n+1)

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

    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)

    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1)
 
print(dp[n])

 

2. 2Xn 타일 - 실버3

~로 나눈 나머지를 구하는 문제는 DP 먼저 떠올리기!

점화식 찾기

n = int(input())

# 가로 1로 1개 or 가로 2로 2개
dp = [0] * (n+1)

if n <= 3:
    print(n)
else:
    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)

 

3. 2Xn타일2 - 실버3

점화식 찾기

런타임 에러난 코드

n = int(input())

dp = [0] * (n+1)

dp[1] = 1
dp[2] = 3
if n < 3:
    print(dp[n])
else:
    for i in range(3, n+1):
        dp[i] = dp[i-2] * 2 + dp[i-1]

    print(dp[n] % 10007)

-> 이렇게 푸니까 99%에서 런타임 에러가 났다

why? n = 1일때, dp[2] = 3 부분에서 인덱스 초과가 나기 때문이다.

당연한 이유인데 조금 더 꼼꼼히 예외를 생각하는 사고를 가지자.

 

맞은 코드

import sys
input = sys.stdin.readline

n = int(input())

dp = [0] * (n+1)

dp[1] = 1

if n < 2:
    print(dp[n])
elif n == 2:
    print(3)

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

    print(dp[n] % 10007)

4. 123더하기 - 실버3

점화식 찾기

def dp123(n):
    dp = [0 for _ in range(n+1)]
    if n < 3:
        return n
    elif n == 3:
        return 4
    else:
        dp[1] = 1
        dp[2] = 2
        dp[3] = 4
        for i in range(4, n+1):
            dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
        return dp[n]

c = int(input())

for i in range(c):
    n = int(input())
    print(dp123(n))

5. 로봇 조종하기 

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

# dp
n, m = map(int, input().split())

graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

dp = [[-1e9] * m for _ in range(n)]
left = [[-1e9] * m for _ in range(n)]
right = [[-1e9] * m for _ in range(n)]

dp[0][0] = graph[0][0]

for j in range(1, m): # 0행 작업
    dp[0][j] = dp[0][j-1] + graph[0][j]

for i in range(1, n):
    # 왼 -> 오
    left[i][0] = dp[i-1][0] + graph[i][0]
    for j in range(1, m):
        left[i][j] = max(dp[i-1][j] + graph[i][j], left[i][j-1] + graph[i][j])

    # 오 -> 왼
    right[i][m-1] = dp[i-1][m-1] + graph[i][m-1]
    for j in range(m-2, -1, -1):
        right[i][j] = max(dp[i-1][j] + graph[i][j], right[i][j+1] + graph[i][j])

    # merge
    for j in range(m):
        dp[i][j] = max(left[i][j], right[i][j])

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

+ 추가예정