글 읽기 - 파이썬 시간 초과 질문드립니다.

seongkwangz 1년 전 0

pypy로 해도 시간초과가 뜨는데 어떻게 해야 시간 안에 문제를 풀 수 있는지 알려주실 분 계신가요?

다른 질문들을 찾아봐도 어떻게 해야할지 감이 안잡힙니다

def solve(n, x, y):
    global result
    if n == 2:
        if x == r and y == c:
            print(result)
            return
        result += 1
        if x == r and y + 1 == c:
            print(result)
            return
        result += 1
        if x + 1 == r and y == c:
            print(result)
            return
        result += 1
        if x + 1 == r and y + 1 == c:
            print(result)
            return
        result += 1
        return
    
    solve(n / 2, x, y)
    solve(n / 2, x, y + n / 2)
    solve(n / 2, x + n / 2, y)
    solve(n / 2, x + n / 2, y + n / 2)
        
    

N, r, c = map(int, input().split())
result = 0
solve(2**N, 0, 0)

siyamaki 1년 전 0

해당 재귀함수들이 20번째줄의 return문에 막혀서 실행이 안됩니다

solve(n / 2, x, y)

solve(n / 2, x, y + n / 2)

solve(n / 2, x + n / 2, y)

solve(n / 2, x + n / 2, y + n / 2)

seongkwangz 1년 전 0

근데 저렇게 해줘야 답이 잘나옵니다. return을 없애면 에러가 납니다

<b>RecursionError</b>: maximum recursion depth exceeded in comparison

siyamaki 1년 전 1

올려주신 코드에는 solve 재귀함수가 if N == 2: 안에 들어가 있는걸로 보입니다

seongkwangz 1년 전 0

오타 지적 감사드립니다:)

siyamaki 1년 전 1

solve를 들어가실 때 행/열 + n만큼에 포함되지 않은 부분은 재귀로 들어갈 필요가 없습니다. 해당 부분만 분기 처리 해주시면 될듯하네요

그러면 재귀로 들어가지 않은 부분은 n*n 칸만큼 result에 더해주기만 하면 됩니다.

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

문제

문제

출처

ICPC

파이썬 시간 초과 질문드립니다.

seongkwangz 1년 전 0

siyamaki 1년 전 0

seongkwangz 1년 전 0

siyamaki 1년 전 1

seongkwangz 1년 전 0

siyamaki 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말