글 읽기 - 계속 런타임에러랑 메모리초과가 뜨는데... 잘못된 부분좀 알려주세요 ㅠㅠ

hwpark12 2년 전 1

점화식을

a(n) = a(n-1) + b(n-1)

b(n) = 2*a(n-1) + b(n-1)

으로 세우고 a(n) + b(n) 이 전체 경우 수라고 두고 풀었는데... 재귀함수 호출 횟수때문에 오류가 생기는걸까요...?

어떻게 고쳐야할지 알려주세요 ㅠㅠ

a = {1:1, 2:3}
b = {1:2, 2:4}
def lionsA(n):
    if n in a:
        return a[n]
    
    a[n] = lionsA(n-1) + lionsB(n-1)
    return a[n]

def lionsB(n):
    if n in b:
        return b[n]
    
    b[n] = 2*lionsA(n-1) + lionsB(n-1)
    return b[n]

m = int(input())
print(lionsA(m)%9901+lionsB(m)%9901)

Green55 2년 전 1

sys.setrecursionlimit를 써보세요

hwpark12 2년 전 1

import sys 해서 리밋을 늘리니까 런타임에러가 메모리초과로 바뀌더라고요...

값을 조절해봐도 계속 둘 중 하나가 뜨는데 어떻게 해야 할까요...?

Green55 2년 전 1

재귀 대신 반복문을 사용하는 바텀업 방식을 사용해보세요

alsrjs0725 2년 전 3

숫자를 저장할때 그대로 저장하시면 후반으로 갈수록 숫자가 너무 커져서 메모리를 과다하게 사용하게 됩니다 이를 방지하기 위해서 중간중간 나머지 연산을 통하여 숫자의 용량을 줄여주셔야 합니다

https://www.acmicpc.net/proble...

이 방식이 왜 정답인지 궁금하시다면 위 문제를 풀어보시길 바랍니다

그리고 18번째 줄에서 lionsA(m)%9901+lionsB(m)%9901 라고 하시면 둘을 더했을때 9901 이상이 될 수 있습니다 둘을 더한 후 나머지 연산을 해주셔야 합니다

import sys
sys.setrecursionlimit(100001)
a = {1:1, 2:3}
b = {1:2, 2:4}
def lionsA(n):
    if n in a:
        return a[n]
    
    a[n] = (lionsA(n-1) + lionsB(n-1))%9901
    return a[n]

def lionsB(n):
    if n in b:
        return b[n]
    
    b[n] = (2*lionsA(n-1) + lionsB(n-1))%9901
    return b[n]

m = int(input())
print((lionsA(m)+lionsB(m))%9901)

hwpark12 2년 전 1

아... 나머지 연산을 해줘야 메모리가 줄어드는군요!!! 문제 추천까지 정말 감사합니다 ㅠㅠ

두분 모두 감사드립니다!!!

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

문제

문제

출처

ICPC

계속 런타임에러랑 메모리초과가 뜨는데... 잘못된 부분좀 알려주세요 ㅠㅠ

hwpark12 2년 전 1

Green55 2년 전 1

hwpark12 2년 전 1

Green55 2년 전 1

alsrjs0725 2년 전 3

hwpark12 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말