[프로그래머스] 피로도 - 파이썬

문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

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

입출력

80

[[80,20],[50,40],[30,10]]

3

입출력 예 설명

현재 피로도는 80입니다.

만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면

• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.
• 남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.

만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면

• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
• 남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.

따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.

---

솔루션

1. DFS 풀이

백준이랑 다른 프로그래머스는 함수 형태로 코드를 완성해야 하니까 solutoin 함수 아래에 dfs 함수를 만들어주었다.

DFS랑 백트래킹이랑 호환하면 좋다.

여기서 dfs를 돌릴때 초기에 cnt를 0으로 두고 재귀 로직 들어갈때 cnt+1을 늘려주고 재귀 끝나면 visited[i] = False로 백트래킹 해준다.

 

def solution(k, dungeons):
    def dfs(k, dungeons, visited, cnt):
        max_cnt = cnt
        for i in range(len(dungeons)):
            needs, outs = dungeons[i]
            if not visited[i] and k>=needs: # 피로도 남아있을때
                visited[i] = True
                max_cnt = max(max_cnt, dfs(k-outs, dungeons, visited, cnt+1))
                visited[i] = False # 백트래킹
        return max_cnt
    visited = [False] * len(dungeons)
    
    return dfs(k, dungeons, visited, 0)

 

동작 예시로 이해하기

입력: k = 80, dungeons = [[80,20], [50,40], [30,10]]

초기 호출: dfs(80, dungeons, [False, False, False], 0)

1. i=0 ([80,20]):
   • visited[0] = True → visited = [True, False, False]
   • dfs(60, dungeons, [True, False, False], 1) 호출
     • i=1 ([50,40]):
       • visited[1] = True → visited = [True, True, False]
       • dfs(20, dungeons, [True, True, False], 2) 호출
         • i=2 ([30,10]):
           • 20 < 30이므로 탐험 불가, 반환 2
       • visited[1] = False → visited = [True, False, False]
     • i=2 ([30,10]):
       • visited[2] = True → visited = [True, False, True]
       • dfs(50, dungeons, [True, False, True], 2) 호출
         • i=1 ([50,40]):
           • visited[1] = True → visited = [True, True, True]
           • dfs(10, dungeons, [True, True, True], 3) 호출 → 반환 3
           • visited[1] = False → visited = [True, False, True]
       • visited[2] = False → visited = [True, False, False]
   • visited[0] = False → visited = [False, False, False]
2. i=1 ([50,40]):
   • visited[1] = True → visited = [False, True, False]
   • (이하 비슷하게 진행)

분석

• 재귀 깊이 들어갈 때:
  • [80,20] → [50,40]을 방문하면 visited = [True, True, False]가 됩니다.
  • 이때 [30,10]은 탐험 불가라 재귀가 종료되고, visited[1] = False로 돌아와 [True, False, False]가 됩니다.

 

---

2. 순열 풀이

from itertools import permutations

def solution(k, dungeons):
    max_cnt = 0
    

    for perm in permutations(dungeons, len(dungeons)):
        current_k = k # 현재 피로도 초기화
        cnt = 0 # 이번 순열에서 탐험한 던전수
        
        for need, out in perm:
            if current_k >= need:
                current_k -= out
                cnt += 1
            else:
                break
        max_cnt = max(cnt, max_cnt)
    return max_cnt