DP 실전문제

 

1. 프로그래머스 - N으로 표현

https://school.programmers.co.kr/learn/courses/30/lessons/42895 

 

아이디어)

dp[i] = N을 i번 사용해서 만들 수 있는 숫자들의 집합

i번 사용했을때 가능한 숫자들은, i-1번까지 사용한 숫자들과 사칙연산을 통해 계산

ex)

- dp[1] = { 5 }  : 5를 한번만 사용

- dp[2] = N을 2번 이어붙인  수+ 이전연산과의 사칙연산 조합

{ 55, 5+5, 5-5, 5/5, 5*5 } :  55, dp[1]과의 사칙연산조합

- dp[3]은 dp[1]과 dp[2]의 조합

{ 555, 55+5, 55-5, 55*5, 55/5, 10+5, 10-5, 10*5, 10/5, ..... }

- dp[4]는 dp[1]과 dp[3]의 조합

- dp[5]는 dp[1]과 dp[4]의 조합 or dp[2]와 dp[3]의 조합

 

이를 반복하여 dp[i]에서 number가 발견되는 순간, 최소한 횟수 반환

 

def solution(N, number):
    dp = [set() for _ in range(9)] # dp[1] ~ dp[8] 사용
    # N을 여러 번 이어붙인 경우는 미리 dp에 넣어준다
    # ex. dp[1] = {5}, dp[2] = {55}, dp[3] = {555}
    for i in range(1, 9):
        dp[i].add( int(str(N)*i) )

    # dp[i] : i번 사용한 결과는 dp[j]와 dp[i-j]의 조합
    # ex. dp[5] = dp[1]+dp[4] or dp[2]+dp[3] or dp[3]+dp[2] or dp[4]+dp[1]
    for i in range(1, 9):
        for j in range(1, i):
            for op1 in dp[j]:
                for op2 in dp[i-j]:
                    dp[i].add(op1+op2)  #덧셈
                    dp[i].add(op1-op2)  #뺄셈
                    dp[i].add(op1*op2)  #곱셈
                    if op2 != 0:
                        dp[i].add(op1//op2) #나눗셈

        if number in dp[i]:
            return i
    

    return -1 # 8까지 사용했는데도 못찾은 경우는 return되는게 없고, 여기서 -1을 반환한다

 

 

 

2. 프로그래머스 - 등굣길

https://school.programmers.co.kr/learn/courses/30/lessons/42898

# 이 문제는 행,열이 반대로 표기되어 있어 유의해야 함!!!
# dp는 행열을 반대로 표기해서 평소대로 생각하자
def solution(m, n, puddles):
    dp = [ [0]*(m+1) for _ in range(n+1) ]
    dp[1][1] = 1
    puddles = [[y,x] for [x,y] in puddles]  # 행/열이 반대로 표기되어 있어

    # 위에서 오거나, 왼쪽에서 오거나 둘 중 하나
    for i in range(1,n+1):
        for j in range(1,m+1):
             if i==1 and j==1: continue
             if [i, j] in puddles:
                dp[i][j] = 0
             else:
                dp[i][j] = ( dp[i-1][j] + dp[i][j-1] ) % 1000000007
    
    return dp[n][m]

 

 

 

3. 프로그래머스 - 정수 삼각형

https://school.programmers.co.kr/learn/courses/30/lessons/43105

 

2차원 dp로 해결

dp를 트리 모양대로 초기화 하고, 모양대로 합을 차례로 더해감

- 트리의 양 끝 요소는 더하는데 문제없으나 가운데 끼인 요소는 더할 수 있는 경우가 2가지 존재

- 합이 더 큰 경우만 dp에 저장한다

>> 완성된 dp의 맨 마지막 배열이 삼각형 최종 누적 합이고, 이 중 가장 큰 값이 정답

def solution(triangle):
    N = len(triangle)
    dp = [[0]*len(row) for row in triangle]
    dp[0][0] = triangle[0][0]

    # 삼각형 각 층을 순차적으로 탐색
    for i in range(1, N):
        for j in range(len(triangle[i])):
            if j == 0: #삼각형 맨 왼쪽 (위에서 하나만 더할 수 있음)
                dp[i][j] = dp[i-1][j] + triangle[i][j]
            elif j == len(triangle[i]) - 1: #삼각형 맨 오른쪽 (위에서 하나만 더할 수 있음)
                dp[i][j] = dp[i-1][j-1] + triangle[i][j]
            else: # 삼각형 중간 - 위에서 두 값 중 큰 값을 더함
                dp[i][j] = max( dp[i-1][j-1], dp[i-1][j] ) + triangle[i][j]
            
    return max(dp[-1])