글 읽기 - DFS를 사용하여 풀어봤는데 시간초과가 아닌 메모리 초과라서 여쭤봅니다

kgood1 3년 전 0

다익스트라를 활용하여 푸는 문제라고 하는데

문제를 보자마자 dfs로 n까지 가는 모든경로를 생각하여 n까지 갈때 쓰인 비용이 m이하이면

dp[비용]에 최소시간을 갱신해서 dp[m]일때의 값을 구하는 다이나믹 프로그래밍 방식을 사용해봤습니다

그런데 시간초과로 틀린것이 아닌 메모리 초과로 틀려서 여쭤보게 되었습니다

dfs를 사용할때 많은 메모리가 사용되는건가요???

(pypy3)를 사용했습니다.

import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline
INF=sys.maxsize
T=int(input())

def dfs(a, sum, time):
    if a == n:
        dp[sum] = min(dp[sum], time)
        return
    for b, c, d in adj[a]:
        if check[b]:
            continue
        else:
            sum += c
            if sum > m:
                sum -= c
                continue
            time += d
            check[b] = True
            dfs(b, sum, time)
            check[b] = False
            sum -= c
            time -= d
    return

for _ in range(T):
    n,m,k=map(int,input().split())
    adj=[[]for _ in range(n+1)]
    for _ in range(k):
        a,b,c,d=map(int,input().split())
        adj[a].append((b,c,d))
    dp=[INF]*(m+1)
    # 방문 확인
    check=[False]*(n+1)
    check[1]=True
    dfs(1,0,0)
    # dp[m]을 최솟값 만들기
    for i in range(1,m+1):
        dp[i]=min(dp[i],dp[i-1])

    if dp[m]==INF:
        print('Poor KCM')
    else:
        print(dp[m])

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

문제

문제

출처

ICPC

DFS를 사용하여 풀어봤는데 시간초과가 아닌 메모리 초과라서 여쭤봅니다

kgood1 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말