바위 뚫는중

[프로그래머스] Lv2. 피로도 - 완전탐색, 순열 본문

Algorithms/프로그래머스

[프로그래머스] Lv2. 피로도 - 완전탐색, 순열

devran 2023. 10. 6. 23:03
반응형

https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=python3

풀이

순열? Permutation

서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것

위 문제에서 던전의 길이가 최대 8이하로 주어지므로 최대 8! 의 경우의수가 있음

from itertools import permutations 순열을 활용하여 모든 경우의 수를 구한다!

from itertools import permutations

def solution(k, dungeons):
    answer = -1
    
    for p in permutations(dungeons, len(dungeons)):      
        hp = k #현재 체력
        cnt = 0 #돌 수 있는 던전의 수
        
        for x, y in p: #x는 p[0] y는 p[1]를 뜻함 각각 최소, 소모
            if hp >= x:
                hp -= y
                cnt += 1
        
        answer = max(answer,cnt) # 순열당 더 큰 cnt로 answer를 지정한다
    
    return answer

예시를 참고로 순열을 생성하면

([80, 20], [50, 40], [30, 10])
([80, 20], [30, 10], [50, 40])
([50, 40], [80, 20], [30, 10])
([50, 40], [30, 10], [80, 20])
([30, 10], [80, 20], [50, 40])
([30, 10], [50, 40], [80, 20])

위와 같은 경우의 수가 나오고 이때 p는 한줄을 뜻한다. 순열 한줄!

p의 x,y라 하면 각각 한줄 안의 요소의 첫째값 둘째값을 뜻함

반응형