나의 풀이
First Thoughts
- 어떤 기준에 따라
sort하면 최적 방법을 찾을 수 있지 않을까? (e.gkey = lambda x : x[1]) -> 실패 - 그냥
bruteforce로 모든 경우의 수에 대해서 다 따져보자!- 이를 위해서 itertools에서 permutations을 불러와서 모든 경우의 수를 따져주었다.
- math.perm()과는 달리 모든 경우의 수를 보여줘서 각 요소의 내용을 다뤄야할 때에는 매우 편리하다.
from itertools import permutations as p
def solution(k, dungeons):
ans = 0
for dg in p(dungeons):
hp = k
cnt = 0
for d in dg:
if d[0] > hp:
break
hp -= d[1]
cnt += 1
ans = max(cnt, ans)
return ans
DFS 을 이용한 풀이
전혀 상상도 하지 못했는데 DFS을 이용한 풀이도 가능했다. 키포인트는 visited[j]를 1로 지정했다가 다시 0으로 바꿔주는 작업!
한번에 이해하기엔 조금 어려운 코드였는데 line-by-line으로 이해해보자.
- def solution(k, dungeons)
이 부분은 input을 받고 dfs을 실행시키는 함수라 쉽게 이해 가능하다.
- dfs(k, cnt, dungeons)
-
for j in range(N)은 dungeons에서 어떤 곳부터 탐험할지 정하는(=즉 starting point을 정하는) 역할을 한다. -
if문을 통해 기본 조건을 만족하는지 확인하고 - 만족하는 경우에 탐험을 실시했으니 visited[j]=1로 지정한다. 이후 나머지 탐험을 위해서 dfs 재귀 함수를 실행한다.
- j가 1,2,…인 경우에도 탐험을 실시해줘야 하므로 visited[j]를 0으로 초기화해준다. (일종의 backtrack)
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
위 코드에서 이해가 잘 되지 않았던 부분은 왜 dfs에 dungeons을 반복해서 인자로 전달하지?였다. 그냥 global 변수에 dungeons을 지정하고 그냥 불러오면 될 것 같다. 이런 아이디어를 적용한 코드는 다음과 같다.
answer = 0
N = 0
visited = []
dg = []
def dfs(k, cnt):
global answer
if cnt > answer:
answer = cnt
for j in range(N):
if k >= dg[j][0] and not visited[j]:
visited[j] = 1
dfs(k - dg[j][1], cnt + 1)
visited[j] = 0
def solution(k, dungeons):
global N, visited, dg
dg = dungeons
N = len(dg)
visited = [0] * N
dfs(k, 0)
return answer
그런데 사실 dfs 방식이 더 효율적이냐? 그건 아닌 듯 하다. 물론 이 문제가 더 복잡화되어서 (실제 게임처럼) tree 모양처럼 뻗어나가는 경우까지 일반화할 수 있다는 점에서 의미가 있다.