프로그래머스 고득점 kit(유형정리) - 피로도

코딩테스트 연습 - 피로도 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

• 피로도

문제 설명

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

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

제한사항

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

입출력 예kdungeonsresult

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입니다.

 

 

문제는 이와 같다. 문제를 보면서 이해는 쉽게 할 수 있을 것인데 관건은 순서대로 탐험하는 것이 아니라는 것이다.

1->2->3, 1->3->2 ... 등 가능한 경우의 수를 모두 탐험하고 최대 탐험 수를 구하는 것이다. 그렇다면 두 가지의 알고리즘을 떠올릴 수 있다.

 

1) 순열

2) DFS

 

DFS는 브루트포스에 조금 맞지 않는다는 생각에 순열을 이용하기로 했다.

 

 

※ 알고리즘

1. 순열을 이용하므로 permutations를 불러온다.

2. dungeons 배열에서 len(dungeons) 길이에 맞는 경우의 수를 순열로 모조리 뽑는다.

3. [최소 필요 피로도, 소모 피로도] 순서대로 순열에서 조사하여 k(현재 피로도) 보다 최소 필요 피로도가 작거나 같으면 현재피로도에서 소모피로도를 계속 빼준다. 그리고 count를 1씩 더해준다.

4. 최대 탐험 수를 구해야 하므로 max나 count와 answer를 비교하는 알고리즘을 사용하여 최대 탐험 수를 갱신시켜준다. 

 

from itertools import permutations

def solution(k, dungeons):
    answer = 0
    
    for per in permutations(dungeons, len(dungeons)):
        tmp = k
        count = 0
        
        for min_tired, spend_tired in per:
            if tmp >= min_tired:
                tmp -= spend_tired
                count += 1
        
        if count > answer:
            answer = count
            
    return answer

 

이렇게 해결해 볼 수 있었다. 기존 위의 문제에서 permutations를 사용해 본 경험이 있어서 쉽게 경우의 수 알고리즘을 떠올릴 수 있었다. 이 문제를 풀 때 처음에는 tmp = k를 따로 해 주지 않고 k와 최소 필요 피로도를 비교하는 식으로 알고리즘을 짰으나 경우가 1개씩 모자라는 현상을 발견했다.

 

한동안 고민하다 k의 기존 값을 보존해 주지 않으면 계속 k 값이 변경되는 것을 눈치채고 tmp = k 로 k 본연의 값을 보존해 주었다.

 

Brute Force 문제는 단순히 for문으로 전체를 본다는 알고리즘이지만, 경우의 수를 모두 조사해야 하는 이와 같은 유형의 문제도 있으므로 순열도 항상 생각해 두어야 할 듯 하다.