Programmers_피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946

---

문제 파악

피로도 시스템에 기반하여 던전을 돌 때마다 피로도가 감소한다. 이렇게 감소된 피로도로 또 다시 던전을 돌고 이렇게 반복하여 가장 많이 돌 수 있는 던전의 수를 찾는다.

접근 방법

던전을 돌면서 피로도를 감소시키고 이를 반복문으로 처리해서 풀면 되겠다고 생각했으나 이럴 경우 주어진 리스트대로의 던전 횟수가 나오게 되어서 백트래킹으로 바꿔서 풀었다.

+0719

만약 3개의 던전을 간다고 하자. 그렇다면 [1,2,3] 이렇게 있다면 1→2→3 , 1→3→2, 2→1→3… 이렇게 모든 던전을 방문하는 방법을 정하고 이는 순열으로 생각할 수 있다.

이 문제는 모든 던전 케이스를 순서대로 나열한 후 각 case마다 탐험하는 던전 수를 구해서 가장 큰 값을 리턴해주면 된다. 즉, 순열을 이용하면 문제를 풀 수 있다.

던전의 순서를 고려해서 최대한 많이 탐험할 수 있는 경우를 찾아야 하는 것인데, 순열을 통해 모든 가능한 순서를 탐색하는 방식으로 해결할 수 있다. 던전의 순서가 바뀌면 결과가 달라질 수 있기 때문에 순열을 통해 모든 경우를 시도해봐야 한다.

코드 구현

def solution(k, dungeons):
    # 기본값 세팅
    n = len(dungeons)
    visited = [0] * n
    answer = 0

    def backtracking(k, count):
        # 최대 count를 answer에 저장
        nonlocal answer
        if count > answer:
            answer = count

        # dungeons 순회
        for i in range(n):

            # 1. 방문한 적 없고
            # 2. 현재 피로도가 던전의 필요 피로도보다 크거나 같으면
            if not visited[i] and k >= dungeons[i][0]:
                # i번째 원소 방문
                visited[i] = True
                # 백트래킹 함수 호출
                backtracking(k - dungeons[i][1], count + 1)
                # i번째 원소 pop
                visited[i] = False

    backtracking(k, 0)
    return answer

백트래킹을 통해 방문하고 방문을 하지 않았거나 피로도가 가능할경우 다시 백트래킹을 통해 방문해서 최대로 많이 돌 수 있는 던전의 수를 뽑아냈다.

배우게 된 점

• 0704

  def solution(k, dungeons):
      answer = 0
      
      for i in range(len(dungeons)):  
          if k >= dungeons[i][0]:     
              answer += 1
              k -= dungeons[i][1]     
      
      return answer

처음에는 반복문으로 풀면 되겠다고 잘못 접근해서 쉬운 문제라고 생각했는데 이럴 경우에는 최대 던전 횟수가 아닌 주어진 리스트대로의 던전 횟수가 나오게 된다. 그래서 백트래킹으로 풀어야겠다고 생각하고 코드를 다시 짜게 되었다.

지금까지는 백트래킹에 대해 순열, 조합 등 가벼운 로직만 구현하다가 실제로 문제를 풀게 되었는데 원리는 이해가 가지만 실제로 내 손으로 코드를 뽑아내는 과정이 쉽지 않다. 강의를 다시 듣고 좀 더 공부해봐야 겠다.

• 0719

  def solution(k, dungeons):
      # 기본값 세팅
      n = len(dungeons)
      visited = [0] * n
      answer = 0
  
      def backtracking(k, count):
          # 최대 count를 answer에 저장
          # 오류!
          if count > answer:
              answer = count
  
          # dungeons 순회
          for i in range(n):
  
              # 1. 방문한 적 없고
              # 2. 현재 피로도가 던전의 필요 피로도보다 크거나 같으면
              if not visited[i] and k >= dungeons[i][0]:
                  # i번째 원소 방문
                  visited[i] = True
                  # 백트래킹 함수 호출
                  backtracking(k - dungeons[i][1], count + 1)
                  # i번째 원소 pop
                  visited[i] = False
  
      backtracking(k, 0)
      return answer

answer 변수가 함수 내부에 정의되어 있는 반면, bcaktracking 함수 내부에서 answer을 참조하려고 하기 때문에 오류가 뜬다. 함수 내부에서 함수 외부에 있는 변수를 참조하고 수정하려고 할 때는 nonlocal 키워드를 통해서 명시적으로 참조해야 한다.