[프로그래머스/Python] 피로도

문제

프로그래머스 - 피로도

해결 과정

• idx: 던전의 번호
• cnt: 총 던전의 개수
• 가장 바깥의 for문: 총 던전의 개수에서 1씩 줄여가는 반복문
• 중간 for문: 최대 던전의 개수가 i일 때 방문 순서의 조합들을 방문하는 반복문
  • now: 현재 피로도
  • check: 최대 던전의 수인지 확인해주는 플래그
• 가장 안쪽의 for문: 해당 순서로 피로도를 계산하는 반복문
  • 현재 필요도보다 최소 필요 필요도가 크다면
    check는 False로 방문할 수 없는 던전이 있으니까
    최대 던전 수로 i를 가질 수 없다는 것
  • 현재 필요도보다 최소 필요 필요도가 같거나 작다면
    현재 피로도에 소모 필요도를 뺀다.
• check가 True라는 것은 최대 던전 수를 i로 모두 방문했다는 것이므로 retrun i

시행착오

• 최대 던전 수를 구해야함 -> 던전의 개수에서 하나씩 줄여가며 확인한다.
  -> while문을 사용하여 순열을 구하니까 시간초과가 났다 -> for문을 사용하라

풀이

from itertools import permutations
def solution(k, dungeons):
	# 던전의 번호: 0, 1, 2
    idx = [i for i in range(len(dungeons))]
    # 던전의 개수
    cnt = len(dungeons)
    
    # 최대 던전의 수에서 1씩 줄여간다: 3,2,1
    for i in range(cnt,0,-1):
    	# i개일 때의 던전의 순열을 구한다.
        for order in permutations(idx,i):
            now = k
            check = True
            for o in order:
                if dungeons[o][0] > now:
                    check = False
                    break
                else: 
                    now -= dungeons[o][1]
            if check:
                return i

다른 풀이 (백트래킹)

answer = 0
N = 0
visited = []

# 매개변수: 피로도, 방문한 던전의 수, 던전의 배열
def dfs(k, cnt, dungeons):
    global answer
    # 최대 던전의 수
    if cnt > answer:
        answer = cnt
        
    for j in range(N):
        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