[동적계획법(DP)] 모음_코딩테스트 고득점 Kit

N으로 표현

링크텍스트

def solution(N, number):
    s = [set() for x in range(8)]
    for i, x in enumerate(s, start = 1):
    	x.add(int(str(N) * i))
    for i in range(1, len(s)):
    	for j in range(i):
        	for op1 in s[j]:
            	for op2 in s[i - j - 1]:
                	s[i].add(op1 + op2)
                    s[i].add(op1 - op2)
                    s[i].add(op1 * op2)
                    if op2 != 0:
                    	s[i].add(op1 // op2)
        if number in s[i]:
        	answer = i + 1
            break
    else:
    	answer = -1
    return answer

정수 삼각형

링크텍스트

import sys

n = int(sys.stdin.readline())

# 다이나믹 프로그래밍을 위한 DP 테이블 초기화
array = []
for _ in range(n):
    array.append(list(map(int, sys.stdin.readline().split())))

# 다이나믹 프로그래밍으로 2번째 줄부터 내려가면서 확인
for i in range(1, n):
    for j in range(i+1):
        # 현재 위치가 가장 왼쪽일 경우
        if (j==0):
            array[i][j] += array[i-1][j]
        # 현재 위치가 가장 오른쪽 일 경우
        elif (j==i):
            array[i][j] += array[i-1][j-1]
        # 나머지 경우
        else:
            array[i][j] += max(array[i-1][j-1], array[i-1][j])

# 마지막 행에서 최대값을 출력
print(max(array[n-1]))

등굣길

링크텍스트

def solution(m, n, puddles):
    # 1부터 시작하는 (1,1) ~ (n, m) 2차원 배열
    memo = [[0 for _ in range(m+1)] for _ in range(n+1)] # 0으로 초기화

    # 주의 ! - 문제에서 주어지는 row, col는 반대!
    for col, row in puddles:
        memo[row][col] = -1 # 갈수 없는 물 웅덩이 표시
    memo[1][1] = 1 # 출발 지점 1로 지정

    def dp(row, col):
        if row < 1 or col < 1 or memo[row][col] < 0:
            return 0
        # 이미 계산한 값이 있으면 값을 바로 가져옴
        if memo[row][col] > 0:
            return memo[row][col]

        memo[row][col] = dp(row, col-1) + dp(row-1, col)
        return memo[row][col]

    return dp(n, m) % 1000000007