[완전탐색 / 프로그래머스] 87946번 : 피로도(다시)

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

 

문제 이해

1. 해당 던전을 탐색하려면 해당 던전의 0인덱스 값 이상의 k 값을 가지고 있어야한다. 해당 던전을 지나가면 1인덱스의 값만큼 k가 줄어든다 

2. 최대한 많은 던전을 탐색해야한다. 그러기 위해선 큰 진입 피로도 던전부터 시작하고, 적게 피로도가 감소하는 방향으로 가야한다 

 

search()함수의 작접

1. cnt_list에 전달받은 cnt값을 추가한다

2. dungeons 요소를 하나씩 확인하면서, 만약 현재 최소 필요 피로도가 k보다 작거나 같다면 temp_list에 dungeon 리스트를 복사한다

3. 이후 temp_list의 현재 인덱스 값(i)를 삭제한다

4. search()함수를 재귀 호출하여 반환받은 값을 cnt_list에 추가한다

5. cnt_list 리스트에 존재하는 값 중 최댓값을 반환한다

 

즉, 던전에 들어갈 때마다 피로도를 감소시키고, 현재 들어간 던전을 제외한 리스트를 다시 search()함수에 전달하여 가장 많이 들어간 값을 반환한다 ????????

 

- 정답 풀이 :

 

참고한 블로그

def solution(k, dungeons) :
    return search(k, dungeons, 0)


def search(k, dungeons, cnt) :
    cnt_list = [cnt]

    for i in range(len(dungeons)) :
        if dungeons[i][0] <= k :
            temp_list = dungeons.copy()
            del temp_list[i]
            cnt_list.append(search(k - dungeons[i][1], temp_list, cnt + 1))

    
    return max(cnt_list)

 

- 시도해본 풀이 :

최대한 많은 던전을 탐색하기 위해 0인덱스와 1인덱스의 차이를 기준으로 내림차순 정렬한 후 탐색 가능한 던전을 탐색한 후 그 수를 세면서 진행했는데 테스트 케이스 몇 개에서 실패했다 

def solution(k, dungeons):
    #해당 피로도랑 기준 피로도랑 제일 차이 많이 안 나면서 감소되는 피로도 제일 적은거
    for i in range(len(dungeons)):
        dungeons[i].append(abs(dungeons[i][0] - dungeons[i][1]))
            
    dungeons.sort(key = lambda x : x[2], reverse = True)

    count = 0
    for dungeon in dungeons:
        a, b = dungeon[0], dungeon[1]
        if k >= a:
            count += 1
            k -= b
    
    return count