프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 13분

from itertools import permutations

def solution(k, dungeons):
    answer = -1
    
    for case in permutations(dungeons,len(dungeons)):
        
        now = [k,0]
        for dungeon in case:
            
            required = dungeon[0]
            used = dungeon[1]
            
            if required<=now[0]:
                now[0] -=used
                now[1] += 1
                
        if answer<now[1]:
            answer = now[1]
        
    return answer

입력된 피로도와 던전별 요구피로도, 소모피로도를 통해 최대로 탐험할 수 있는 던전수를 찾는 완전탐색 문제입니다. 🐬🐬🐬

던전별 요구사항이 존재하기 때문에 순서별 케이스를 구하기 위해 permutations을 활용하여 쉽게 구현할 수 있었습니다.

[다른 사람의 풀이1]

def solution(k, dungeons):
    answer = -1
    queue = deque()
    queue.append((k, []))

    while queue:
        k, route = queue.popleft()
        for i in range(len(dungeons)):
            a, b = dungeons[i]
            if k >= a and i not in route:
                temp = route + [i]
                queue.append((k - b, temp))
            else:
                answer = max(answer, len(route))

    return answer

BFS를 활용하여 피로도를 다 소모하였을 때 던전수를 갱신하는 방식입니다.

[다른 사람의 풀이2]

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 및 백트레킹을 활용한 풀이입니다.

감사합니다.