[프로그래머스] 피로도

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

프로그래머스

---

문제를 보니까 Greedy로도 풀 수 없고, 딱히 최적의 결과가 나오도록 정렬할 수도 없었다.

그래서 완전탐색으로 풀기로 했는데,

주어진 던전 배열의 크기가 매우 작은 걸로 봐서 시간초과가 나지도 않을 것 같았다.

 

간단하게 던전 리스트 원소들을 가지고 순열을 만들어주었다.

매 요소마다 탐험할 수 있는 던전의 수를 계산하고 그 중 최댓값을 리턴하였다.

 

python

from itertools import permutations

def calc(k, ordered_lst):
    result = 0
    for a, b in ordered_lst:
        if a > k or b > k:
            return result
        k -= b
        result += 1
    return result

def solution(k, dungeons):
    answer = 0
    for order in list(permutations(dungeons)):
        answer = max(answer, calc(k, order))
    return answer

 

분명히 더 좋은 방법이 많을 것 같아 다른 분들 풀이를 읽어보았다.

나처럼 순열을 구해서 푼 분들도 꽤 보였지만 dfs풀이가 매우 많았다.

 

---

보고 많이 배운 코드이다.

answer = 0
N = 0
visited = []

def dfs(k, cnt, dungeons):
  print(k, cnt, ":")
  global answer
  answer = max(answer, cnt)

  for j in range(N):
    print("j : ",j)
    if k >= dungeons[j][0] and not visited[j]:
      visited[j] = 1
      dfs(k-dungeons[j][1], cnt+1, dungeons)
      visited[j] = 0
      
def solution(k, dungeons):
  global N, visited
  N = len(dungeons)
  visited = [0] * N
  dfs(k, 0, dungeons)
  return answer

 

 

이런 문제는 여러 번 풀어봐야겠다.