글 읽기 - 다른 방식(top-down)으로 풀이 질문드립니다.

time_to_bye 5년 전 0

안녕하세요.

DP 문제 풀면서 bottom-up, top-down 방식 공부하고 있습니다.

bottom-up으로는 문제를 맞았는데, top-down에서는 런타임 에러가 납니다.

문제에서 n 조건이 1<=n<=10000이니까 top-donw에서 사용하는 재귀로 해결 할 수 없어서 런타임에러 인지 질문드립니다.

n = int(input())
wine = [0]
for i in range(n):
    wine.append(int(input()))

# bottom - up 방식

dp = [[0 for j in range(3)] for i in range(n+1)]
dp[1][1] = wine[1]

for i in range(2, n+1):
    dp[i][0] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2])
    dp[i][1] = max(dp[i-2][0], dp[i-2][1], dp[i-2][2]) + wine[i]
    dp[i][2] = dp[i-1][1] + wine[i]

print(dp)
print(max(dp[n]))

# top-down 방식

dp = [[None for j in range(3)] for i in range(n+1)]
dp[0] = [0, 0, 0]
dp[1] = [0, wine[1], 0]

def calc_dp(n1, n2):
    if dp[n1][n2] is None:
        dp[n1][0] = max(calc_dp(n1-1, 0), calc_dp(n1-1, 1), calc_dp(n1-1, 2))
        dp[n1][1] = max(calc_dp(n1-2, 0), calc_dp(n1-2, 1), calc_dp(n1-2, 2)) + wine[n1]
        dp[n1][2] = calc_dp(n1-1, 1) + wine[n1]

    return dp[n1][n2]

calc_dp(n, 0)
print(dp)
print(max(dp[n]))

djm03178 5년 전 0

아럐와 같은 문장을 맨 위에 추가하면 됩니다.

그리고 가능하면 문제가 되는 코드를 그대로 올려주세요.

import sys
sys.setrecursionlimit(100000)

time_to_bye 5년 전 0

답변 주셔서 감사합니다. 도움주신 방법대로 해결하였습니다.

그리고 처음 질문글을 써서 미숙하게 남겼습니다.

다음에 질문 글 올릴 때는 말씀하신대로 올리도록 하겠습니다.

감사합니다.!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

다른 방식(top-down)으로 풀이 질문드립니다.

time_to_bye 5년 전 0

djm03178 5년 전 0

time_to_bye 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말