완전히 탐색해야할때는..

1. 문제

 

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

코딩테스트 연습 - 피로도

 

xx게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다.

 

이 때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다.

 

"최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다.

 

예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

 

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다.

 

유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons가 매개변수로 주어질 때, 유저가 탐험할 수 있는 최대 던전 수를 return하세요

 

2. 제한사항

 

k는 1이상 5000이하인 자연수

 

dungeons의 세로(행)길이(던전의 개수)는 1이상 8이하

 

dungeons의 가로(열)길이는 2

 

dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"]

 

"최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같음

 

"최소 필요 피로도"와 "소모 피로도"는 1이상 1000이하인 자연수

 

서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있음

 

3. 입출력 예시

 

그림1. 입출력 예시 설명

 

4. 나의 풀이

 

이런 문제 가장 간단한 방법은 모든 경우의 수를 따져서 검사하는 방법

 

그러나 효율적인지 아닌지 먼저 고민해야함

 

최대한 많은 던전을 탐험할려면 가장 먼저 최소 필요 피로도가 높은 던전을 탐험해야한다는 것은 분명함

 

최소 필요 피로도가 작은 던전을 탐험하다가 피로도를 소모해버리면 최소 필요 피로도가 높은 던전을 충분히 돌 수 있는데도 못도는 경우가 분명히 생길거

 

그래서 dungeons를 먼저 정렬하는데 최소 필요 피로도가 가장 높으면서 소모 피로도가 가장 낮은 순서대로 정렬하기로 함

 

특히 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있다는 조건에 기반해서 set()을 이용해서 중복을 먼저 제거했음

 

def solution(k, dungeons):
    
    dungeons = sorted(list(set([tuple(dungeon) for dungeon in dungeons])),key=lambda item: [-item[0],item[1]])
    
    a,b = dungeons.pop(0)
    
    if k >= a:
        
        k = k - b
        
        max_exp = 1
        
        ind = True
    
    else:
        
        dungeons.append([a,b])
        
        max_exp = 0
        
        ind = False

 

근데 이게 제한사항에 dungeons 안에 던전들 중 최소 필요 피로도가 현재 피로도 k보다 항상 작다는 보장이 없었음

 

그래서 가장 최소 필요 피로도가 높은 던전을 먼저 뽑아낸다음에 돌 수 있으면 돌고 돌 수 없으면 dungeons에 집어 넣음

 

그러면 이제 다음은 무엇을 돌아야하는가? 최소 필요 피로도가 가장 높은 던전을 먼저 돌았다고 생각을 해보면

 

[50,40]과 [30,10]중에서 최소 필요 피로도가 높은 던전을 먼저 돌아야한다고 생각할 수 있지만 소모 피로도가 높아버리면 최소 필요 피로도가 작은 던전을 돌 수 없는 경우가 생긴다

 

그래서 [80,20]을 먼저 돌면 현재 k=60인데 최소 필요 피로도가 높은 [50,40]을 돌아서 k=20이 되어서 [30,10]을 돌 수가 없음

 

그러면 소모 피로도가 작은 던전을 먼저 돌아야하는가?? [30,10]을 돌고 나서 [50,40]을 돌면 가능하지만...

 

만약에 [[80,30],[50,40],[30,10]]이라고 한다면 [80,30]을 돌고 k=50이 되어 [30,10]을 돌면 k=40이 되어 [50,40]을 돌 수가 없음

 

그러니까 소모 피로도가 작은 던전을 먼저 돌아서 전부 돈 것은 우연히 가능했다

 

그래서 결과적으론 최소 필요 피로도가 작은 던전을 돌아야하는가??

 

소모 피로도가 작은 던전을 먼저 돌아야하는가?? 등등 매 순간 최적의 방법을 생각해봤지만

 

반례가 생겨서 모든 경우의 수를 따져야한다는 것이 합리적이다.

 

 

from itertools import permutations
    
per_dungeons = permutations(dungeons)

for duns in per_dungeons:

    if ind:

        exp = 1

    else:

        exp = 0

    now_k = k

    for dungeon in duns:

        if now_k >= dungeon[0]:

            now_k = now_k - dungeon[1]

            exp += 1

        else:

            pass

    if exp >= max_exp:

        max_exp = exp 

return max_exp

 

itertools의 permutations 함수를 사용하면 리스트에서 모든 순열의 수를 구해준다

 

그래도 최소 필요 피로도가 가장 높은 던전을 먼저 돌아야 최대한 많은 던전을 돌 수 있는 것은 분명해서

 

돌고 나서 permutation을 계산하면 시간을 줄일 수 있을 것이라고 예상을 했음

 

그래서 최소 필요 피로도가 가장 높은 던전을 먼저 돌았다면 ind=True여서 exp=1로 시작하고 아니라면 exp=0으로 시작함

 

이렇게 모든 permuation을 검사해서 나온 max_exp를 return하면 끝

 

근데 이렇게 하면 실패하는 케이스가 생김

 

왜 그런지 생각해보면 최소 필요 피로도가 가장 높은 던전을 먼저 돈다는 가정이 틀린거

 

최소 필요 피로도가 가장 높은 던전이 우연히 소모 피로도가 상당히 높아서 충분히 더 돌 수있는데도 다른 던전을 못도는 경우가 분명히 생길거임

 

예를 들어 [[80,70],[50,40],[30,10]] 이러면 [80,70]을 돌면 k=10으로 1번만 도는걸로 끝인데

 

[50,40],[30,10] 2개를 돌면 k=80 >> k=40 >> k= 30 남고도 2번으로 더 많이 돌 수 있음

 

그래서 그냥 처음부터 모든 경우의 수를 따지는게 맞다

 

def solution(k, dungeons):
    
    dungeons = list(set([tuple(dungeon) for dungeon in dungeons]))
    
    from itertools import permutations
    
    per_dungeons = permutations(dungeons)
    
    max_exp = 0
    
    for duns in per_dungeons:
        
        exp = 0
        
        now_k = k
        
        for dungeon in duns:
            
            if now_k >= dungeon[0]:
                
                now_k = now_k - dungeon[1]
                
                exp += 1
            
            else:
                
                pass
        
        if exp >= max_exp:
            
            max_exp = exp 
        
    return max_exp

 

처음에 set()을 이용해서 중복을 제거하고..(중복은 명백히 둘중 하나만 돌 수 있을테니까)

 

itertools의 permutations로 모든 순열의 수의 리스트 per_dungeons를 구한 다음에

 

모든 순열의 수 각각 duns에 대해 검사를 해서 몇번이나 던전을 돌 수 있는지 계산해본다

 

그 중에서 최댓값 max_exp를 return

 

 

5. 되돌아보기

 

완전 탐색하는 것이 현명할 때가 분명히 있다

 

사실 근데 코딩테스트 할때는 일단 완전 탐색 해보고 나서 효율성을 통과 못하면 효율성을 개선하면 되는거

 

완전 탐색은 효율이 안좋으니까 효율을 좋은 방법으로 코딩하자 이렇게 생각하다가

 

완전 탐색도 정답인데 효율 좋은 방법을 생각 못해서 문제 못맞추는거면 너무 아쉬우니까