[프로그래머스] 피로도

입출력 예

k	dungeon	result
80	[[80,20],[50,40],[30,10]]	3

체력이 k dungeon 리스트에서 각 요소들의 첫번째 요소는 필요한 최소 체력, 두번째는 사용되는 체력이다.

k체력으로 최대 던전을 몇번 돌 수 있는지 파악하는 것이 문제이다.

 

조건:

dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.

• dungeons의 가로(열) 길이는 2 입니다.

해당 조건을 보았을 때 완전 탐색이 가능할 듯하다.

 

이 문제를 두가지의 방법으로 생각했다.

1. 3가지를 뽑는 순열의 인덱스로 완전 탐색

2. dfs를 이용한 완전탐색

 

이중 파이썬 itertools라이브러리의 permutations를 사용하여 인덱스 뽑기 후 완전 탐색을 하였다.

 

from itertools import permutations

def solution(k, dungeons):
    answer = -1

    permulist = list(permutations(range(len(dungeons)), len(dungeons)))
    #여기 순열로 이용해서 모든 인덱스 조합을 찾아주는 것이 포인트

    for per in permulist:
        tempk = k
        tempanswer = 0
        for i in per:
            if tempk >= dungeons[i][0]:
                tempk -= dungeons[i][1]
                tempanswer += 1
            if tempanswer > answer:
                answer = tempanswer

    return answer

 

입출력 예시에서 dungeon의 길이는 3이기 때문에 모든 던전을 도는 순열의 인덱스를 뽑으면

[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]

가 나오고 모두 돌았을 때 이 중 가장 답의 크기가 큰 경로가 답이 된다.

 

*dfs 방식보다 빠를 듯 하다.