피로도 lv2

🌈문제 링크

<풀이방법 2개>
1. 백트랙킹
2. 순열 & 연산

k : 현재 피로도
count : 던전 수
dungeon : 던전 정보
visitted : 방문여부

1. 백트랙킹

DFS —> 여기서는 한번에 던전을 갈 수 있는 끝까지 탐색한 후 이전 단계로 돌아가는 작업

info 함수를 먼저 정의, 밑에서 solution 함수가 info 함수를 호출해 결과를 반환

max_count = 0

def dfs(k, count, dungeons, visited):
    global max_count 
    if count > max_count:
        max_count = count
    
    for i in range(len(dungeons)):
        if visited[i] != 1 and k >= dungeons[i][0]:
            visited[i] = True
            dfs(k - dungeons[i][1], count + 1, dungeons, visited)
            visited[i] = False
        
def solution(k, dungeons):
    global max_count
    visited = [False] * len(dungeons)
    dfs(k, 0, dungeons, visited)
    return max_count

max_count = 0

def dfs(k, count, dungeons, visited): global max_count

던전 돌 수 있는 최대 횟수 값 초기화로 0으로 설정

원래 dfs 함수 바깥에 있던 max_count를 전역변수인 global로

global max_count로 언급해주면서 안에서도 적용 가능

if count > max_count:

max_count = count

우리가 찾는 것은 최대 던전 돌 수 있는 횟수

if visited[i] != 1 and k >= dungeons[i][0]:

visited[i] = True

만약 던전을 방문 안했고, 현재 피로도 >= 던전을 뛰면서 소모될 피로도 이 경우에

해당 던전을 방문했다고 하여 True

dfs(k - dungeons[i][1], count + 1, dungeons, visited) visited[i] = False

• 재귀적으로 한번 함수 호출 —> dfs(~~)

해당 던전을 방문한 상태에서 남은체력과 방문한 던전수를 가지고 재귀적으로 다음던전 탐색

visited =0 —→ 백트랙킹을 수행해 해당던전을 방문하지 않은 상태로 돌아감

def solution(k, dungeons): global max_count

이제 던전 최대 돌 수 있는 횟수 구합시다!

visited = [False] * len(dungeons)

visited 라는 리스트를 만들되, 리스트의 각 요소를 False 혹은 0 으로 초기화

dfs(k, 0, dungeons, visited) return max_count

0 혹은 False —→ 어떤 던전도 돌지 않은 상태에서 세겠습니다

dfs 알고리즘에서 던전 방문여부 추적한 후, 최대 돌 수 있는 횟수 반환

2. 순열 & 연산

from itertools import permutations
def solution(k, dungeons):
    max_count = 0 
    dungeon_permut = list(permutations(dungeons, len(dungeons))) 
    
    for dungeons_path in dungeon_permut:
        current_hp = k    
        count = 0 
        
        for required_minimum_hp, consume in dungeons_path:
            if required_minimum_hp <= current_hp:
                count += 1
                current_hp -= consume
            elif current_hp < required_minimum_hp:
                break

        if max_count < count:
            max_count = count
    
    return max_count