[프로그래머스] 피로도

문제 이해하기

주어진 피로도(K)를 사용해서 최대한 많은 던전을 탐험하는 문제였다.

던전의 최대 개수가 8개이니 가장 연산이 많은 경우의 수는 65,536이다, 따라서 완전탐색을 사용하면 시간안에 풀 수 있다.

문제 해결 방법 설명하기

1. 모든 경우의 수를 탐색

아래의 코드를 보면 visited 배열을 사용해 던전의 방문 유무를 확인하고, 해당 던전의 피로도 조건을 만족한다면 일단 던전에 입장해서 탐색을 진행한다. 이 방법을 사용하면 모든 경우의 수를 탐색할 수 있다.

def search(k, dungeons, visited):
    ans = 0
    for i in range(len(dungeons)):
        if visited[i] == False and dungeons[i][0] <= k:
            visited[i] = True
            ans = max(ans, search(k - dungeons[i][1], dungeons, visited) + 1)
            visited[i] = False

 

코드

def search(k, dungeons, visited):
    ans = 0
    for i in range(len(dungeons)):
        if visited[i] == False and dungeons[i][0] <= k:
            visited[i] = True
            ans = max(ans, search(k - dungeons[i][1], dungeons, visited) + 1)
            visited[i] = False
            
    return ans

def solution(k, dungeons):
    visited = [False] * len(dungeons)
    return search(k, dungeons, visited)


if __name__ == "__main__":
    k = 80
    dungeons = [[80, 20], [50, 40], [30, 60], [20, 30]]
    print(solution(k, dungeons))  # 3