[프로그래머스] LV.2 피로도(python)

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

프로그래머스

 

 

문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  • dungeons의 가로(열) 길이는 2 입니다.
  • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
  • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

 

문제 해결

from itertools import permutations

def solution(k, dungeons):
    arr = []
    for i in permutations(dungeons, len(dungeons)):
        arr.append(list(i))
    num = []
    for i in arr:
        cnt = 0
        n = k
        for j in i:
            if n >= j[0]:
                n -= j[1]
                cnt += 1
        num.append(cnt)
    return max(num)

 

문제 풀이 설명

완전탐색 문제이다. 모든 경우의 수를 찾아서 확인해봐야하는데 아직 나는 이런거(?)에 쫌 약한거같다..

공부 부족도 맞고 이런 류의 문제를 찾아서 많이 풀어봐야겠다!!

여튼 이번 문제의 로직은 순열을 이용해서 풀었다.

순열(서로다른 n개에서 r개를 선택할때, 순서를 고려해 중복없이 뽑는 경우의 수)으로 모든 경우의 수를 arr 리스트에 append 해주었고, 이중 for문으로 해당 arr 리스트에 접근했다.

cnt 는 각 경우의 수 당 갈 수 있는 던전의 개수를 세는 용도로 사용했고, k를 한 번 써버리면 기준이 되는 현재 피로도를 나타낼 수 없기에 n으로 따로 저장해 현재 피로도를 표현했다.

만약 던전의 최소 필요 피로도보다 현재 피로도보다 작거나 같다면 던전에 입장할 수 있다는 뜻이므로 입장하고, 소모 피로도 만큼 감소시킨다. 모든 던전을 돌게 되었을 때 한 가지의 경우의 수가 끝나며, 해당 경우의 수의 던전의 개수 cnt를 num 리스트에 append 한다.

모든 경우의 수를 돌았을 때 num에는 모든 경우의 수의 던전의 개수가 저장되게 되며, 이중 max()함수를 사용해 최댓값을 return 하게되면 끝이다.