[알고리즘] 프로그래머스 피로도 파이썬

[프로그래머스] LEVEL2 피로도

✅ 문제

✅ 나의 풀이

다른 대안이 생각나지 않았고, 문제의 타입으로 완전탐색이 설정되어 있었기에 순열을 이용해서 모든 경우의 수를 탐색했다.

permutations를 통해서 dungeons 배열 내 탐험할 던전 순서의 모든 경우의 수를 탐색했다. 모둔 경우를 탐색한 후 탐험한 던전 수 total의 최댓값을 구했다.

from itertools import permutations

def solution(k, dungeons):
    answer = -1
    for p in permutations(dungeons, len(dungeons)) :
        total = 0
        left = k
        for i in range(len(p)):
            mn = p[i][0]
            us = p[i][1]
            if left < mn :
                break
            else :
                left -= us
                total += 1
        if answer < total :
            answer = total
    return answer

위 아이디어를 다른 방법으로 구현한 코드도 있었다.

from itertools import permutations
def solution(k, dungeons):
    answer = 0
    
    for p in permutations(dungeons, len(dungeons)):
        tmp = k
        cnt = 0 
        
        for need, spend in p:
            if tmp >= need:
                tmp -= spend
                cnt += 1
        answer = max(answer, cnt)
    return answer

나의 코드와 다른 점은 크게 두 가지 존재한다.

• p 배열 내의 mn과 us 변수를 for문 안에서 할당하기
• max(answer, total)로 크기 비교 + 할당하기

✅ 다른 풀이

순열을 사용하는 방법 외에도 백트래킹을 사용할 수 있다.
for문을 돌면서 일단 GO, 안 되면 BACK.

answer = 0

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

백트래킹은 아직 익숙치 않다 😅

✅ 얻어가기

순열과 조합

from itertools import permutations
from itertools import combinations