[프로그래머스] 피로도

프로그래머스 - 피로도
문제 링크

🤔 접근 방법

'그리디'로 접근하였지만 마땅한 해법이 떠오르지 않아, 완전탐색으로 풀이하였다.

✏️ 구현

순열 라이브러리 사용

for perm in permutations(dungeons, len(dungeons)):

perm은 dungeons에서 dungeons 길이 만큼의 순열을 가지고 있다. 이는 한 번의 탐색에 사용될 한 가지 경우의 순열이라 생각할 수 있다. 즉, 테스트 케이스 하나인 것으로도 볼 수 있다. 따라서 매 테스트 케이스마다 피로도와 카운트를 초기화해야 함을 알 수 있다.

백트래킹 사용

if k >= dungeons[i][0] and not ch[i]:
	ch[i] = 1
  	dfs(k - dungeons[i][1], cnt + 1, dungeons, ch)
  	ch[i] = 0

탐험이 가능한 던전을 최대한 탐험한다. dfs 인자로 변경되는 현재 피로도, 던전 카운트를 넘겨준다.

💻 전체코드

순열 라이브러리 사용

from itertools import permutations

def solution(k, dungeons):
    dun_cnts = []
    for per in permutations(dungeons, len(dungeons)):
        cur_k = k
        dun_cnt = 0
        for p in per:
            if p[0] > cur_k:
                continue
            dun_cnt += 1
            cur_k -= p[1]
        dun_cnts.append(dun_cnt)

    return max(dun_cnts)

백트래킹 사용

answer = 0

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

그리디 풀이
그리디로 잘 풀이한 블로그가 있어서 링크를 남깁니다.
블로그 링크