글 읽기 - [python 3] 1463 메모리초과 도와주세요

choah76 3년 전 0

반례들을 참고해서, 정수X가 2나 3으로 나누어 떨어지는 경우더라도 X-1에서 1을 만들때의 최소값과 X에서 1을 만들때의 최소값을 서로 비교하도록 하였습니다. 그런데 메모리초과 오류가 일어나는데, 어떻게 해야할까요?

N = int(input())
global count,L
L = [-1]*(N+1)
count = 0

import sys
sys.setrecursionlimit(1000000)

def makeone(n) :
    global count,L
    
    if n == 1:
        
        if L[int(n)] > -1 :
            pass
        else :
            L[1] = 0
        
        return count
    
    if n%3 == 0 and n%2 == 0 :
        
        if L[int(n/3)]> -1:
            a = L[int(n/3)]+1
        else :
            a = makeone(n/3)+1
            L[int(n/3)] = a-1
        
        if L[int(n-1)]> -1:
            b = L[int(n-1)]+1
        else :
            b = makeone(n-1)+1
            L[int(n-1)] = b-1
            
        if L[int(n/2)]> -1:
            c = L[int(n/2)]+1
        else :
            c = makeone(n/2)+1
            L[int(n/2)] = c-1
        
        count += 1
        L[int(n)] = min(a,b,c)
        return min(a,b,c)
        
    elif n%3 == 0:
        
        if L[int(n/3)]> -1:
            a = L[int(n/3)]+1
        else :
            a = makeone(n/3)+1
            L[int(n/3)] = a-1
        
        if L[int(n-1)]> -1:
            b = L[int(n-1)]+1
        else :
            b = makeone(n-1)+1
            L[int(n-1)] = b-1
        
        count += 1
        L[int(n)] = min(a,b)
        return min(a,b)
        
    elif n%2 == 0:
        
        if L[int(n/2)]> -1:
            a = L[int(n/2)]+1
        else :
            a = makeone(n/2)+1
            L[int(n/2)] = a-1
        
        if L[int(n-1)]> -1:
            b = L[int(n-1)]+1
        else :
            b = makeone(n-1)+1
            L[int(n-1)] = b-1
        
        count += 1
        L[int(n)] = min(a,b)
        return min(a,b)
    
    else :
        
        if L[int(n-1)]> -1:
            b = L[int(n-1)]+1
        else :
            b = makeone(n-1)+1
            L[int(n-1)] = b-1
        
        count += 1
        L[int(n)] = b
        return b


print(makeone(N))

choah76 3년 전 0

위의 코드처럼 탑-다운방식으로 풀지말고, 바텀-업방식으로 푼다면 메모리초과도 해결하고 알고리즘도 간결하게 짤 수 있는것을 확인했습니다!

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

문제

문제

출처

ICPC

[python 3] 1463 메모리초과 도와주세요

choah76 3년 전 0

choah76 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말