DP

틀린 문제 리뷰

1. 계단오르기

계단 오르기

- 2번 연속해서 계단을 오른 경우와 1번 연속해서 계단을 오른 경우의 최대값을 dp배열을 통해 구한다.

- 전을 밟지 않은것 최대(dp[i-2]) + 현재계단(arr[i]) , 전전을 밟지 않은 것 최대(dp[i-3]) + 전 계단(arr[i-1]) + 현재계단(arr[i])

dp[i] = max(dp[i-3] + arr[i-1] + arr[i], dp[i-2] + arr[i])

2. 가장 ~ 하는 부분 수열

1. 가장 긴 감소하는 수열

2.가장 큰 증가 부분 수열

이것이 왜 dp인가?

나는 이 쉽게 생기면서 어려웠던 이유는 그냥 앞에서 뒤에꺼를 보고 그냥 오면 되는거 아닌가?

이런 생각을 했었다...

그러다 문득 생각난것은 "가장 큰 증가 부분 수열"을 보고 생각이 났다.

이유는 예를 들어 

1 100 2 50 60 3 5 6 7 8

이러한 수가 있을 경우 1다음 100을 바로 먹으면 뒤에 있는 50, 60을 먹을 수 없다....

그러니 미래를 알 수 없는 찜찜한 느낌 + 조건만 만족하면 전꺼를 써먹어서 사용가능 하겠는데...??이런 느낌을 받았다...

하는 방법은 for문을 두번 돌려 아래와 같이 지금 내가 바라보고 있는 것 의 전 꺼 중에 있는 것을 써먹으면 된다...!!!

3. 퇴사 2

퇴사 2

내가 푼 방법은 Top-Bottom방식으로 풀었다

그런데 인터넷에 더 좋은 방식이 있어서 작성한다.

내가 푼 방식

import sys

input = sys.stdin.readline

N = int(input())
arr = [[0]*2 for _ in range(N+1)]
dp = [0] * (N+1)

for i in range(1, N+1):
    a,b = map(int, input().split())
    arr[i][0] = a
    arr[i][1] = b

if arr[N][0] == 1: dp[0] = arr[N][1]

for i in range(1,N+1):
    time,price = arr[N-i]
    if time-1 > i: dp[i] = dp[i-1]
    else: dp[i] = max(dp[i - time] + price, dp[i-1])

print(dp[N])

다른 풀이 방식

아래 방식은 Bootom -> Top방식을 사용하였다.

아래 방식은 먼저 한칸 뒤에 계산을 하므로 +1을 해주었다.

 

import sys

input = sys.stdin.readline

N = int(input())
arr = [[0]*2 for _ in range(N+2)]
dp = [0] * (N+2)

for i in range(1, N+1):
    a,b = map(int, input().split())
    arr[i][0] = a
    arr[i][1] = b

for i in range(1, N+1):
    if dp[i] < dp[i-1]:
        dp[i] = dp[i-1]
    if i + arr[i][0] < N+2:
        if dp[i + arr[i][0]] < dp[i] + arr[i][1]:
            dp[i+arr[i][0]] = dp[i] + arr[i][1]

print(max(dp))

4. 내리막길

내리막길

이 문제는 dp라는 느낌보다는 dfs 문제에 가깝다고 느껴진다.

원래는 최적의 길을 찾는 문제는 visit + bfs 로 문제를 푸는데

이 문제는 dp + dfs 문제로 문제를 푼다.

나는 재귀를 리턴하는 것은 피해왔는데 그러질 말아야겠다고 생각된다....

이 문제와 비슷한 문제를 프로그래머스에서 봤던거 같은데 그문제도 찾으면 정리하겠다.

from collections import deque
import sys

input = sys.stdin.readline
n, m = map(int, input().split())
map = [list(map(int, input().split())) for _ in range(n)]
dp = [[-1] * m for _ in range(n)]
dic = [[1,0],[-1,0],[0,1],[0,-1]]

def dfs(sy, sx):
    if sy == n-1 and sx == m-1:
        return 1

    if dp[sy][sx] != -1:
        return dp[sy][sx]

    depth = 0
    for d in dic:
        y,x = sy+d[0], sx+d[1]
        if 0 <= y < n and 0 <= x < m:
            if map[sy][sx] > map[y][x]:
                depth += dfs(y,x)

    dp[sy][sx] = depth
    return dp[sy][sx]


print(dfs(0,0))