Skip to main content

87946 - 피로도

info
  • 문제 보기: 87946 - 피로도
  • 소요 시간: 17분 20초
  • 풀이 언어: python
  • 체감 난이도: 2️⃣
  • 리뷰 횟수: ✅

풀이 키워드​

스포주의

완전탐색 dp


풀이 코드​

info
  • 메모리: 9420 KB
  • 시간: 73 ms
import sys
sys.setrecursionlimit(10**6)

d = []
visited = []

def dp(ddx, k):
    global visited
    ans = [0]
    for i in range(len(d)):
        req, cost = d[i][0], d[i][1]
        if req <= k and not visited[i]: # 최소 피로도 ok
            visited[i] = True
            ans.append(dp(i, k-cost) + 1) # 피로도 소모
            visited[i] = False
        
    return max(ans)

def solution(k, dungeons):
    global d, visited
    d = dungeons
    visited = [False for _ in range(len(d))]
    ans = [0]
    for i in range(len(d)):
        if d[i][0] <= k and not visited[i]: # 최소 피로도 ok
            visited[i] = True
            ans.append(dp(i, k-d[i][1]) + 1) # 피로도 소모
            visited[i] = False
    
    return max(ans)

풀이 해설​

던전 수가 최대 8개여서 무지성 완탐 들박이 가능하다.

이 경우, n개의 던전을 모두 어느 순서로든 방문할 수 있을만큼 피로도가 충분한 최악의 상황을 가정할 때

nPn = n! 이므로 O(n!)O(n!) 이라는 매우 살벌한 시간복잡도를 가지게 된다.


메모​

  • 함수명을 dp라고 해놨지만 사실 dp가 아닌 그냥 완탐임.

    • 오랜만에 무지성 제출 1트 컷했다.

  • dp 최적화가 먹히려면 일정 조건에서 패스해도 된다는 증명이 필요함.