[완전 탐색] 피로도

피로도

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.
이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
• dungeons의 가로(열) 길이는 2 입니다.
• dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
• "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
• "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
• 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

입출력 예

k	dungeons	result
80	[[80,20],[50,40],[30,10]]	3

---

풀이

입력값이 작으면 완탐으로 풀 것

# dfs(재귀) 
def solution(k, dungeons):
    answer = 0
    answerlist=[0]
    def dundfs(k2,dun2,count2):
        print("k2 :",k2,"dun2 :", dun2, count2)
        for i in range(len(dun2)):
            if i<len(dun2)-1 and k2>=dun2[i][0] 
            and k2>=dun2[i][1]:
                dundfs(k2-dun2[i][1],dun2[:i]+dun2[i+1:],
                count2+1)
            elif i==len(dun2)-1 and k2>=dun2[i][0] 
            and k2>=dun2[i][1]:
                dundfs(k2-dun2[i][1],dun2[:i],count2+1)
        answerlist.append(count2)

    count=0
    for i in range(len(dungeons)):
        print(i)
        if i<len(dungeons)-1 and k>=dungeons[i][0] and 
        k>=dungeons[i][1]:
            dundfs(k-dungeons[i][1],
            dungeons[:i]+dungeons[i+1:],count+1)
        elif i==len(dungeons)-1 and k>=dungeons[i][0] and 
        k>=dungeons[i][1]: # 마지막 리스트
            dundfs(k-dungeons[i][1],dungeons[:i],count+1)
    answer=max(answerlist)

from collections import deque
def solution(k, dungeons):
 L,n,dp = len(dungeons),0,deque()
 dp.append([k,[]])
 while dp:
     p,v=dp.popleft()
     for i in range(L):
         [a,b]=dungeons[i] # 파이썬의 구조분해할당
         if i not in v and p>=a and p-b>=1: 
         dp.append([p-b,v+[i]])
         else : n=max(n,len(v))
 return n

# 던전의 순서를 바꿔가며 최대한 많이 던전 탐험 => dfs ?, 순열(순서가 있는 조합)  
# 순서가 있는 조합을 순열 => permutaions
from itertools import permutations
def solution(k, dungeons):
 answer = 0 
 
 # 모든 가능한 던전 순열을 생성하고 각각에 대해 검사
 for p in permutations(dungeons, len(dungeons)): # 반복객체(n), 뽑는 갯수(r)
     #print(p)
     tmp = k  # 남은 에너지를 나타내는 변수 초기화
     cnt = 0  # 현재 순열에서 통과한 던전 수 초기화

     for need, spend in p:
         if tmp >= need:  # 충분한 에너지가 있을 때
             tmp -= spend  # 던전을 통과하고 남은 에너지 계산
             cnt += 1 
     if cnt > answer:
         answer = cnt
     
 return answer

# solution_1 pick or not + 탐욕법으로 풀이
def solution(k, dungeons):
  """
  탐욕 알고리즘을 적용하기 위해, 남은 피로도를 기준으로 내림차순 정렬
  정렬을 진행하면 pick or not pick으로 선택하는 로직을 적용할 수 있습니다.
  시간복잡도는 O(2^N)
  """
  # 던전들을 시작 에너지와 소모 에너지의 차이에 따라 내림차순으로 정렬합니다.
  # 이렇게 하면 우선적으로 가장 에너지 소모가 큰 던전부터 탐색하게 됩니다.
  dungeons.sort(key=lambda x: x[0] - x[1], reverse=True)
  print(dungeons)
  # 깊이 우선 탐색 (DFS) 방법으로 가능한 모든 던전 조합을 탐색하는 함수를 정의합니다.
  def dfs(idx, passed, answer, k):
      
      # 모든 던전을 확인했을 경우, 지금까지 통과한 던전의 최대 개수를 업데이트 합니다.
      if idx == len(dungeons): # 3
          answer = max(answer, passed)
          return answer
      
      # 현재 탐색하려는 던전을 지정합니다.
      dungeon = dungeons[idx]
      
      # 현재 던전을 통과할 충분한 에너지가 있을 경우,
      # 해당 던전을 통과하면서 필요한 에너지를 소비하고 다음 던전으로 넘어갑니다.
      if k >= dungeon[0]:
          answer = dfs(idx + 1, passed + 1, answer, k - dungeon[1]) # 60 # 50 # 10 
      
      # 현재 던전을 통과하지 않고, 다음 던전으로 그대로 넘어갑니다.
      answer = dfs(idx + 1, passed, answer, k)
      
      return answer

  # 초기 인덱스와 에너지, 그리고 통과한 던전의 개수를 0으로 설정하고 dfs 함수를 호출합니다.
  return dfs(0, 0, 0, k)