문제를 읽으면서 완전탐색 문제라고 생각했다. 그 이유는 제한사항 중 던전의 개수를 보면 알 수 있는데 던전의 개수는 1이상 8 이하이다. 즉, 완전탐색 방식으로 풀어도 메모리 초과와 시간 초과를 걱정하지 않아도 된다는 것이다.
완전탐색 문제는 문제 조건만 맞다면 코드 구현은 매우 간단하다. 단순히 모든 경우의 수를 탐색해주면 된다.
완전탐색 방법이 무식해보여도 때로는 최고의 방법인 경우도 있다는 것을 기억하자!
완전탐색 풀이 코드
import itertools
def solution(k, dungeons):
answer = 0
nPr = list(itertools.permutations(dungeons, len(dungeons)))
for i in nPr:
kk = k
result = 0
for j in i:
if kk < j[0]:
continue
elif kk >= j[0]:
kk -= j[1]
result += 1
answer = max(result, answer)
return answer모든 경우의 수를 찾기 위해서 순열을 사용했다.
순열이란?
몇 개를 골라 순서를 고려해 나열한 경우의 수를 말한다. 즉, 서로 다른 n 개 중 r 개를 골라 순서를 정해 나열하는 가짓수이며 순열이라는 의미의 영어 ‘Permutation’의 첫 글자 P를 따서 nPr로 표시한다
이때 permutations의 인자는 (순열을 생성할 리스트, 리스트에서 고를 원자의 수)이다.
순열을 사용해 던전을 도는 모든 경우의 수를 찾아주고 그 중 던전을 가장 많이 도는 경우의 값이 정답이 된다.
물론 이렇게 완전탐색으로도 풀 수 있지만 dfs를 사용해도 간단하게 풀 수 있다.
DFS 풀이 코드
N = 0
answer = 0
visited = []
def dfs(k, dungeons, cnt):
global answer
if cnt > answer:
answer = cnt
for j in range(N):
if k>=dungeons[j][0] and not visited[j]:
visited[j] = True
dfs(k - dungeons[j][1], dungeons, cnt+1)
visited[j] = False
def solution(k, dungeons):
global N, visited
N = len(dungeons)
visited = [False]*N
dfs(k, dungeons, 0)
return answer그러나 개인적인 생각으로 이 문제는 완전탐색 알고리즘으로 푸는 것을 의도한 것 같다.
^~^