글 읽기 - 백트래킹 사용했는데 시간초과가 발생하네요 ㅠㅠ

tjsgh1512 1년 전 0

재귀호출로 백트래킹을 사용했는데 시간초과가 발생했습니다.

왜 시간초과가 발생하는지 모르겠습니다. ㅠㅠㅠ

import sys
sys.setrecursionlimit(100000)
n = int(input())
cnt = 0
def backtracking(n,data):
    global cnt
    if len(data) >= n:
        cnt += 1
        return 
    else:
        for num in range(int(data[-1]),10):
            if int(data[-1]) <= num:
                backtracking(n,data+str(num))
        return
                
for i in range(10):
    backtracking(n,str(i))
print(cnt)

nahwasa 1년 전 0

백트래킹으로 풀 수 있는지 다시 한번 생각해보세요.

현재 7~9 line을 보면 해당하는 수를 찾을 때 마다 cnt가 1씩 증가되고 있는데,

N이 40만 되도 7line에 걸리는 횟수가 20억번이 넘습니다. 즉 그것만 해도 대략 20초 이상 걸린다는건데, 이후 기하급수적으로 횟수가 늘어나고 N은 1000까지 가능해야 합니다.

tjsgh1512 1년 전 1

그렇네요,,, 동적 프로그래밍이 답이겠네요 ,, 감사해요

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

문제

문제

출처

ICPC

백트래킹 사용했는데 시간초과가 발생하네요 ㅠㅠ

tjsgh1512 1년 전 0

nahwasa 1년 전 0

tjsgh1512 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말