[코테] 경우의 수 고려하기 - Dynamic Programming

Top-down

knapsack 문제를 탑다운 DP (재귀)로 풀어보자

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

# item의 위치와 무게를 index로 하는 2차원 list dp 테이블에 누적 value 값을 저장해서 기억한다

def recur(cur, w):
    global ans
    if w > weight_limit:
        return -9999999

    if cur == n:
        return 0

    if dp[cur][w] != -1:
        return dp[cur][w]

    dp[cur][w] = max(recur(cur+1, w + arr[cur][0]) + arr[cur][1], recur(cur + 1 , w))

    return dp[cur][w]


n, weight_limit = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

dp = [[-1 for _ in range(100_001)] for _ in range(n)] # 2차원 리스트 -> 무게 & 선택 물건 개수 트래킹 

print(recur(0, 0))

Bottom-up

knapsack 문제를 바텀업 DP (점화식)로 풀어보자

import sys
input = sys.stdin.readline

n, weight_limit = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

dp = [[-1 for _ in range(100_001)] for _ in range(n)] # 2차원 리스트 -> 무게 & 선택 물건 개수 트래킹 

for idx in range(n):
    for weight in range(weight_limit+1):
        if weight > weight_limit:
            dp[idx][weight] = dp[idx-1][weight]
        else:
            dp[idx][weight] = max(dp[idx-1][weight-arr[idx][0]] + arr[idx][1], dp[idx-1][weight])

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

1. 확인해야하는 모든 지점을 방문한다.

2. 방문한 뒤에 이동할 수 있는 모든 경우의 수를 재귀로 구현한다.

3. 재귀로 구현한 뒤 재사용 가능한 부분에 대해 DP로 바꾼다.

예시 1) 2차원 배열이 주어졌을 때 기존 숫자보다 큰 숫자를 가진 칸으로 최대한 많이 이동하는 경우

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

n = int(input())

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

def recur(y, x):
    if dp[y][x] != 0: # dp 재사용
        return dp[y][x]

    for dy, dx in [[0,1], [0,-1], [1,0], [-1,0]]: # 상하좌우 이동
        ey = y + dy
        ex = x + dx

        if 0 <= ey < n and 0 <= ex < n:
            if graph[y][x] < graph[ey][ex]: # 현재보다 큰 숫자의 칸으로만 이동
                dp[y][x] = max(dp[y][x], recur(ey, ex) + 1) # dp에 직접 count

    return dp[y][x]

dp = [[0 for _ in range(n)] for _ in range(n)]

for y in range(n):
    for x in range(n):
        recur(y, x)

print(max(map(max, dp)) + 1) # 2차원 배열에서 최대값 찾기

예시 2) 2차원 배열이 주어졌을 때 (0, 0) 지점에서 기존의 숫자보다 작은 숫자가 있는 칸으로만 이동해서 마지막 지점 (n, m)에 도달하는 총 경우의 수

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

Y, X = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(Y)]
dp = [[-1 for _ in range(X)] for _ in range(Y)]
count = 0

def recur(y, x):
    if dp[y][x] != -1: # 모든 지점 중에서 한 번이라도 지나갔다면 재사용
        return dp[y][x]

    if y == Y - 1 and x == X - 1: # 목적지에 도착했을 때만 1을 리턴
        return 1

    route = 0    
    for dy, dx in [[0,1], [0,-1], [1,0], [-1,0]]:
        ey = y + dy
        ex = x + dx

        if 0 <= ey < Y and 0 <= ex < X:
            if graph[y][x] > graph[ey][ex]:
                route += recur(ey, ex)
    dp[y][x] = route  
    return dp[y][x]

print(recur(0, 0))