No Limitation
[완전탐색-DFS] 피로도 본문
https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=python3
본 문제는 완전 탐색 카테고리에 해당하는 문제.
사실 이 문제를 푸는 다른 방법이 생각나지 않아 일단 DFS로 구현해보았는데 당연히 시간 초과가 날 줄 알았음.
하지만, 막상 돌렸을 때는 통과가 됨. 나중에 찾아보니 대부분 비슷하게 푸신 듯.
다만 주의해야 하는 부분은, dfs를 돌아갈 때 마지막에 탐색하지 못하는 던전 케이스에 대해 return할 때는 count를 1을 누적시키면 안되므로 이 부분을 조심해서 구현해야 할 듯.
import copy
def DFS(fatigue,current,dung,cnt) :
## 이 경우는 count를 해주면 안되는 경우
if fatigue < current[0] :
return cnt-1
if not dung :
return cnt
fatigue -= current[1]
result = 0
for i in range(len(dung)) :
d = copy.deepcopy(dung)
d.remove(dung[i])
result = max(result,DFS(fatigue,dung[i],d,cnt+1))
return result
def solution(k, dungeons):
maxs = 0; cnt = 0; result = 0;
for i in range(len(dungeons)) :
dung = copy.deepcopy(dungeons)
dung.remove(dungeons[i])
result = max(result,DFS(k,dungeons[i],dung,cnt+1))
return result
'프로그래밍' 카테고리의 다른 글
[구현] A와 B (백준 12904) (0) | 2024.04.01 |
---|---|
[구현] 삼각달팽이 - 공부용 (0) | 2024.04.01 |
[최대 힙 기초] 이중우선순위큐 (1) | 2024.03.30 |
[BFS] 트리의 부모 노드 찾기 (0) | 2024.03.28 |
[BFS] 일자 기준에 따른 counting (0) | 2024.03.27 |