[프로그래머스]피로도

[49] 피로도

책 구매하기

문제 정보

• 분류: 백트래킹
• 정답률: 60%
• 권장 시간 복잡도: O(N!)
• 핵심 키워드: 순열 탐색, 백트래킹, 피로도, 방문 배열
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/87946

문제를 읽을 때 체크할 포인트

던전 수가 작기 때문에 가능한 방문 순서를 전부 시도해 보는 문제다. 현재 피로도로 들어갈 수 있는 던전만 고르면서 깊이 우선 탐색을 돌리면 된다.

한 번의 선택으로 답이 확정되지 않고, 가능한 경우를 조건에 맞게 잘라 가며 끝까지 봐야 하는 유형이다. 그래서 '무엇을 상태로 들고 갈지'를 먼저 정하는 게 중요하다.

풀이 흐름

1. 방문 여부 배열을 둔다.
2. 현재 피로도로 입장 가능한 던전만 재귀 호출한다.
3. 재귀 깊이마다 방문한 던전 수 최댓값을 갱신한다.

구현할 때 놓치기 쉬운 부분

방문 가능한 던전을 찾는 것만으로는 부족하다. 어떤 순서로 도는지가 최대 방문 수를 바꾸기 때문에, 방문 여부와 현재 피로도를 함께 가지고 모든 경우를 확인해야 한다.

파이썬 정답 코드

def solution(k, dungeons):
  # 방문 여부 배열을 둔다.
  n = len(dungeons)
  visited = [False] * n
  answer = 0

  def dfs(energy, count):
    nonlocal answer
    answer = max(answer, count)

    for i in range(n):
      need, spend = dungeons[i]
      if not visited[i] and energy >= need:
        visited[i] = True
        dfs(energy - spend, count + 1)
        visited[i] = False

  dfs(k, 0)
  # 현재 피로도로 입장 가능한 던전만 재귀 호출한다.
  return answer

시간 복잡도

N은 던전 수이다.

가능한 순서나 배치를 끝까지 시도하는 완전탐색 구조이다. 원소 N개의 순열을 모두 보는 최악의 경우를 기준으로 하면 factorial 차수가 남는다.

따라서 시간 복잡도는 O(N!)이다.