.png&blockId=18f00b21-a9bc-4e35-aeb8-ecb07bddb89a)
1. 접근 방식
1.
바깥으로는 모든 경우의 수를 탐색해야 함 > 경우의 수에서 가지치기 문제 > 순열!
2.
안쪽으로는
a.
if 현재 피로도 ≥ 소모 피로도
•
탐험을 한다.
◦
현재 피로도 = 현재 피로도 - 소모 피로도
◦
탐험 횟수 = 탐험 횟수 + 1
b.
else (현재 피로도 < 소모 피로도)
•
탐험을 종료한다
•
return 탐험 횟수
from itertools import permutations
def solution(k, dungeons):
answer = -1 # 이유?
arr = list(permutations([i for i in dungeons], len(dungeons))) # 모든 경우의 수 탐색
for case in arr:
hp = k # k 초기화
count = 0
for mp in case:
if hp >= mp[0]:
hp = hp - mp[1]
count = count + 1
answer = max(answer, count) # 최대값 갱신
return answer
Python
복사
2. 기본 코드에 대한 설명
•
순열을 활용해 탐색 가능한 모든 경우의 수를 탐색한다.
•
각 탐색에서 현재 피로도가 최소 피로도보다 크다면
◦
현재 피로도 > 최소 피로도
◦
카운트 + 1
•
현재 최대값과 새로운 최대값 비교해서 값 갱신
3. 추가적으로 개선한 코드에 대한 설명
•
사실 처음 생각했던 건 그래프처럼 푸는 거였다. 그런데 아직 푸는 방법을 잘 모른다. .
4. 사용 라이브러리 정리
5. 기타(문제 풀이에 어려웠던 점, 구현하고자 했는데 실패한 방식)
ex) 이 방식으로 접근했는데 구현이 힘들어서 개선했습니다. 그 방식으로 접근했는데 접근방식이 잘못되었다는 것을 깨닫고 다시 풀었습니다.
