[프로그래머스] 고득점Kit (7) - 동적계획법 (파이썬)

1. N으로 표현 (Lv. 3)

# N으로 표현
def solution(N, number):
    arr = [0]
    for i in range(1, 9):
        temp = make(i, N, arr)
        if number in temp:
            return i
        arr.append(temp)
    return -1


def make(i, N, arr):
    result = set()
    temp = int(str(N) * i)
    result.add(temp)
    for half in range(1, i//2+1):
        for x in arr[half]:
            for y in arr[i-half]:
                result.add(x+y)
                result.add(x-y)
                result.add(y-x)
                result.add(x*y)
                if y != 0:
                    result.add(x//y)
                if x != 0:
                    result.add(y//x)
    return result

 

위와 같이 바로 직전의 수식에 사칙연산을 재수행 해주는 방법으로 풀었다.

단, 4일 경우 : 사칙연산의 우선순위를 고려해야한다.

식+식, 식-식, 식*식, 식/식 도 생각해야 한다.

1번 ~ n번의 결과값을 arr에 저장을 하고, n+1번의 값 계산 시에는 1&n, 2&n-1, 3&n-2... 를 전부 계산해야 한다.

 

개인적으로  4가지 문제 중에서 가장 어려웠다.

---

2. 정수 삼각형 (Lv. 3)

# 정수 삼각형
def solution(triangle):
    N = len(triangle)
    for i in range(N):
        triangle[i] = [0] + triangle[i] + [0]
    dp = [[0] * len(x) for x in triangle]
    dp[0][1] = triangle[0][1]
    for i in range(1, N):
        for j in range(1, len(dp[i])-1):
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
    return max(dp[N-1])

 

입력값의 양 끝에 0을 추가해준다.

문제의 조건대로 더한 값들 중 가장 큰 값으로 해당 dp를 업데이트

마지막 dp의 max값 출력

---

3. 등굣길 (Lv. 3)

# 등굣길
def solution(m, n, puddles):
    dp = [[0] * (n+1) for _ in range(m+1)]
    dp[1][1] = 1
    for i in range(1, m+1):
        for j in range(1, n+1):
            if i == 1 and j == 1:
                continue
            if [i, j] in puddles:
                continue
            dp[i][j] = dp[i][j-1] + dp[i-1][j]
    return dp[i][j] % 1000000007

 

 

첫 위치를 1로 초기화를 해두고, 현재 위치에는 왼쪽과 위쪽 값의 합을 저장한다. (왼쪽, 위쪽 = 오른쪽, 아래로만 이동)

웅덩이가 있으면 0이고, dp의 마지막 값을 출력

---

4. 도둑질 (Lv. 4)

# 도둑질
def solution(money):
    dp1 = [0] * len(money)
    dp2 = [0] * len(money)
    dp1[0], dp2[0] = money[0], 0
    for i in range(1, len(money)-1):
        dp1[i] = max(dp1[i-1], dp1[i-2] + money[i])
    for i in range(1, len(money)):
        dp2[i] = max(dp2[i-1], dp2[i-2] + money[i])
    return max(max(dp1), max(dp2))

 

dp를 두 번 실행하면 된다.

dp1 : 첫 집을 방문함, 마지막 집을 방문하지 않음

dp2 : 첫 집을 방문하지 않음, 마지막 집을 방문함

max(전의 dp값, 전전의 dp값 + 현재 money값)으로 초기화

max값을 출력