[프로그래머스]Lv.2 피로도(Python)

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

문제 접근 

 

탐색임에도 불구하고 경우의 수로 풀어도 되는지 모르겠다.

1. dungeons의 모든 경우의 수를 total이라는 리스트를 만들어 저장

2. 각 경우의 수의  던전 수를 total_cnt라는 리스트에 저장

3. 그중 가장 큰 던전의 수를 반환

 

코드

from itertools import permutations  # 가능한 모든 수열의 결과를 순열로 

def solution(k, dungeons):
    answer = 0

    total = []
    total_cnt = []

# print(list(permutations(dungeons,len(dungeons))))

    for i in permutations(dungeons,len(dungeons)):
        total.append(list(i))

    for i in total:
        cnt = 0
        power = k   # 각 경우 돌 때마다 원위치로 만들어야 하므로 
        for j in i:
            if j[0] <= power:
                power -= j[1]
                cnt += 1
        total_cnt.append(cnt)

    answer = max(total_cnt)
    
    return answer

 

 

++ 추가(dfs)

answer = 0

k = 80

dungeons = [[80, 20], [50, 40], [30, 10]]

def DFS(k, dungeons, cnt, check):   # 여기서 cnt는 방문횟수, check는 방문여부
    global answer
    answer = max(answer, cnt)   # answer은 큰 값으로 갱신
    for i in range(len(dungeons)):
        if check[i] == 0 and k >= dungeons[i][0]:   # 아직 방문하지 않은 던전, 현재 피로도가 최소 피로도보다 크면 방문 가능
            check[i] = 1
            DFS(k-dungeons[i][1], dungeons, cnt+1, check)
            check[i] = 0    # 다시 리셋하기

def solution(k, dungeons):
    global answer
    check = [0] * len(dungeons)

    DFS(k, dungeons, 0, check)

    return answer

print(solution(k,dungeons))

회고

 

라이브러리를 계속 사용해도 되는지 의문, 던전의 개수가 1에서 8까지라서 가능하지 그 수가 커지면 해당 방법은 효율성이 떨어질 것이라고 예상