[프로그래머스 87946 파이썬] 피로도 (level 2, 완전 탐색)

알고리즘 유형 : 완전 탐색
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

import sys
from itertools import permutations
INF = sys.maxsize
input = sys.stdin.readline

def solution(k, dungeons):
    answer = -INF
    
    for case in permutations(dungeons):
        fatigue = k
        cnt = 0
        for min_cost, cost in case:
            if fatigue < min_cost:
              break
            else:
                cnt += 1
                fatigue -= cost
        
        answer = max(answer, cnt)
    
    return answer

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

print(solution(k, dungeons))

풀이 요약

1. 이 문제는 규칙이랄게 딱히 보이지 않는다. 최소 필요 피로도의 크기를 기준으로 그리디하게 순회를 하든, 소모 피로도를 기준으로 하든 일반해가 구해지지 않는다. 그래서 완전탐색으로 풀이한다. (k가 최대인 8이어도, 모든 경우의 수는 8! = 약 4만

2. dungeons에 k개의 원소가 있을 떄, k개의 원소를 다 순회하는 모든 경우의 수를 다 돌아본다.

   그 모든 경우의 수는 dungeons의 원소를 대상으로 순열을 구하여 for문으로 순회해주면 된다.

   각 경우의 수(case)에 대해, 첫 번쨰 던전부터 하나씩 접근한다.

   fatigue에 k를 저장해두고, 던전을 순회하면서 소모 피로도를 계속 차감시켜주고 cnt를 1 누적해준다.

   어느 던전에서 fatigue가 min_cost보다 작아지면, 그 때 for를 벗어난 후 그 던전에 대한 cnt와 answer를 max 연산하여 갱신해준다.

   모든 경우의 수를 돈 다음 answer를 출력해주면 된다.

배운 점, 어려웠던 점

• 순열로 모든 경우의 수를 구하여 완전 탐색하겠다고는 생각했는데, 순열 모듈의 사용법이 미숙해서 못 풀었다. 이 문제를 계기로 itertools의 순열, 조합 시리즈를 공부했다. 이 곳에 정리를 아주 깔끔하게 해두셔서 이걸로 공부했다.