글 읽기 - 2579번 질문입니다! (재귀 코드 관련)

rkdgh248 2년 전 0

재귀를 이용해서 해당 문제를 구현해봤는데, 메모리초과나 시간초과도 아니고 그냥 틀렸다고 뜨네요.

문제에 나온 예제 입력이나 제가 임의로 입력한 값을 넣었을 때도 출력은 알맞게 나오는 것 같습니다.

그런데 왜 틀렸다고 뜨는지 모르겠습니다.

혹시 틀린 부분을 찾으시면 알려주세요!

def stair(arr):

    global dp

    n=len(arr)-1
    if dp[n]!=0:
        return dp[n]
    
    else:
        if n==1:
            dp[n]=arr[n]
            return dp[n]
        
        elif n==2:
            dp[n]=arr[n]+arr[n-1]
            return dp[n]

        elif n==3:
            dp[n]=arr[n]+arr[n-2]
            return dp[n]

        else:
            dp[n]=max([stair(arr[:(n-2)])+arr[n]+arr[n-1],stair(arr[:(n-1)])+arr[n]])
            return dp[n]

import sys

arr=[0]

for i in range(int(input())):
    arr.append(int(sys.stdin.readline()))

dp=[0 for _ in range(len(arr))]

print(stair(arr))

lambda 2년 전 0

반례입니다.

output ans input 순입니다.

input은 리스트로 나타냈는데

[2,4,4]라면

input은

입니다.

그리고 stair 함수내부에서 dp=[1,2,3] 처럼 dp자체에 대입하는 경우(dp가 가리키는 대상을 바꾸는 경우)는 없기 때문에 global dp는 필요하지 않습니다.

31 [20, 26, 5]
84 [30, 39, 45]
64 [3, 41, 23]
54 [10, 19, 35]
51 [26, 27, 24]
87 [16, 45, 42]
42 [7, 19, 23]
31 [4, 17, 14]
18 [3, 9, 9]
61 [2, 30, 31]
29 [10, 24, 5]

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

문제

문제

출처

ICPC

2579번 질문입니다! (재귀 코드 관련)

rkdgh248 2년 전 0

lambda 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말