[프로그래머스] 87946번 : 피로도

문제

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

풀이

[프로그래머스] 87946번 : 피로도 🥈(LEVEL2)
⏰ 걸린 시간 : 21분
시간복잡도 : O(N^2)

• 알고리즘 유형 : [완전탐색]
  

✔️ [문제 접근 방법]

0. permutations (순열)을 사용해서 모든 방법을 다 구해서
1. 각각을 방문해서 '최소 필요 피로도'값을 비교해서 '소모 필로도'값을 제거하면서 계산해나간다.
2. 이때 cnt값을 올린후에 answer의 값으로 비교해서 더 크다면 update한다.

✔️ [주의 사항]
0. recursion DFS를 사용한 풀이도 풀어나갈 수 있다.
1. visited[i] = False를 재귀하고 나서 만들어준다.

코드(code)

import itertools
def solution(k, dungeons):
    answer = 0
    permu = list(itertools.permutations(dungeons,len(dungeons)))
    for dungeons in permu:
        cnt = 0
        fatigue = k
        for need_min, use_fatigue in dungeons:
            if fatigue >= need_min and fatigue >=use_fatigue:
                fatigue -= use_fatigue
                cnt +=1
        answer = max(cnt, answer)
          
    return answer

recursion DFS 이용한 코드(code)

answer = 0

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

회고

순열으로 접근하면서 풀면 쉽다. 같은 스터디를 하시는 분 중 DFS로 문제를 푸신분이있다.

• [해당 코드]

  [프로그래머스] 87946번 : 피로도