[Python] 프로그래머스, 피로도 Lv.2 (feat.permutations, 파이썬)

반짝반짝 알고리즘, 인프준

 
 
 
 
 
 
 
 
 
 

피로도

문제 링크

프로그래머스

 

 

문제 설명

이 게임에는 피로도 시스템( 0 이상의 정수로 표현합니다. )이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다.

 
"최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다.
 
예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.
 
이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러 개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다.
 
유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons가 매개변수로 주어질 때, 유저가 탐험할 수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해 주세요
 

 

제한 조건

k는 1 이상 5,000 이하인 자연수입니다.
dungeons의 세로( 행 ) 길이( 즉, 던전의 개수 )는 1 이상 8 이하입니다.

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

 

 
입출력 예

k	dungeons	result
80	[ [ 80, 20 ], [ 50, 40 ], [ 30, 10 ] ]	3

 

입출력 예 설명

현재 피로도는 80입니다.
 
만약, 첫 번째 -> 두 번째 -> 세 번째 던전 순서로 탐험한다면

• 현재 피로도는 80이며, 첫 번째 던전을 돌기 위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 두 번째 던전을 돌기 위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.
• 남은 피로도는 20이며, 세 번째 던전을 돌기 위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.

 
만약, 첫 번째 -> 세 번째 -> 두 번째 던전 순서로 탐험한다면

• 현재 피로도는 80이며, 첫 번째 던전을 돌기 위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 세 번째 던전을 돌기 위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
• 남은 피로도는 50이며, 두 번째 던전을 돌기 위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.

 
따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.
 
 
 
 
 
 
 

---

 
 
 
 
 
 

해결 과정

피로도 문제는 "프로그래머스 > 코딩테스트 고득점 Kit > 완전탐색"에 속해있는 문제입니다. 따라서 모든 경우의 수를 확인해야 하며 dungeons의 최대 길이가 8 이므로 순열로 확인이 가능합니다.
 

[Python] 누적합 / 순열 / 조합 (feat.itertools module)

 
 
1. 결괏값인 최대 던전 수와 모든 던전 탐험 순서를 확인하기 위해 순열을 선언해 주었습니다.
 
2. 모든 순열을 확인하기 위한 for loop 내에서 체력 hp와 던전을 세어줄 값 count를 선언해 주었습니다.
 
3. 순서가 섞인 n번째 던전들의 for loop에서 "최소 필요 피로도"-minimum보다 체력이 작다면 멈추고, 그렇지 않으면 던전 수를 1 증가 후 hp에서 "소모 피로도"-consume을 감소시켜 줍니다. *이때 "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다. 조건이 있기에 hp가 minimum보다 작은지만 비교 가능합니다.
 
4. n번째 던전의 던전 수가 최대 던전 수 max_count보다 크면 갱신해 주고 모든 탐색이 끝나면 max_count를 반환합니다.
 
 
 
 

제출 코드

from itertools import permutations
def solution(k, dungeons):
    max_count = 0 # 최대 던전 수
    permut = list(permutations(dungeons, len(dungeons))) # 던전 탐험 순서의 순열
    
    for ds in permut:
        hp = k    # 체력
        count = 0 # 던전 수
        
        for minimum, consume in ds:
            # 체력이 최소 필요 피로도보다 작으면 break
            if hp < minimum:
                break
            # 아니면 던전 수 1 증가, 소모 피로도 감소
            else:
                count += 1    
                hp -= consume            
            
        # 최대 던전 수보다 크면 갱신
        if max_count < count:
            max_count = count
    
    return max_count

 

 
 
 
 
 
 
 

---

 
 
 
 
 
 
 

또 다른 풀이

백트래킹, Back Tracking

max_count = 0

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

 

[알고리즘] 완전 탐색, 브루트 포스 정의 | 종류 | 장단점 | 예시 (feat. Node.js Brute-Force-Search)

 
 
 
 
 
 
 
 
 
 

---

 
 
 
 
 
 
 
 
 
 

출처: 프로그래머스 코딩 테스트 연습,https://school.programmers.co.kr/learn/challenges