13. 다이내믹 프로그래밍(DP)

N으로 표현 - https://school.programmers.co.kr/tryouts/85952/challenges

dp[0] → i = 1

dp[0] (+-*/) dp[0] → i = 2

dp[0] (+-/) dp[1] = dp[0] (+-/) (dp[0] (+-*/) dp[0]) → i = 3

위 경우 반복해가면서 i=8까지 진행

def solution(N, number):
    if N == number: return 1
    ans = -1
    dp = [{N}]
    
    for i in range(2, 9):
        num_can = {int(str(N)*i)}
        for j in range(0, i-1):
            for x in dp[j]:
                for y in dp[-1-j]: # 둘이 합쳐서 -1 
                    num_can.add(x+y)
                    num_can.add(x*y)
                    num_can.add(x-y)
                    if y != 0:
                        num_can.add(x//y)
        if number in num_can:
            return i
        dp.append(num_can)
    return -1

 

---

등굣길 - https://school.programmers.co.kr/tryouts/85953/challenges

def solution(m, n, puddles):
    puddles = set([(x,y) for x, y in puddles])
    geo = [[0 for _ in range(m+1)] for _ in range(n+1)]
    geo[1][1] = 1
    for i in range(1, n+1):
        for j in range(1, m+1):
            if (j, i) in puddles:
                continue
            # 왼쪽, 위쪽 더해서 전달
            geo[i][j] += geo[i-1][j] + geo[i][j-1]
    return geo[n][m] % 1000000007

 

---

정수 삼각형 - https://school.programmers.co.kr/tryouts/85954/challenges

def solution(triangle):
    n = len(triangle)
    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
    dp[1][1] = triangle[0][0]
    for i in range(2, n+1):
        for j in range(i+1):
            cur_num = triangle[i-1][j-1]
            dp[i][j] = max(dp[i-1][j-1] + cur_num, dp[i-1][j] + cur_num)
    return max(dp[n])