프로그래머스 | 피로도 문제풀이

문제 링크

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

프로그래머스

 

 

문제 접근 방식

최소 필요 피로도, 소모 피로도가 주어진 상황에서 돌 수 있는 최대 던전의 수를 구해야하는 문제. 

던전을 들어가는 모든 경우의 수에 대해 돌 수 있는 던전 수를 구하고,

비교를 통해 최대 던전의 수를 구하는 완전 탐색 문제인 것으로 판단했음.

 

이전 완전 탐색 문제인 카펫과 소수찾기 문제와 달리 재귀함수를 통해 완탐을 진행.

 

처리 과정

각 재귀 과정에서는 

1. 더 돌 수 있는 던전이 없다면 재귀함수를 종료한다.(탈출조건)

2. 남은 던전들을 순회하며 들어갈 수 있는 던전을 찾고, 그 중 가장 많은 수를 도는 던전 수를 구한다.

3. 지금까지의 최대 던전 수를 반환한다.

 

재귀 함수는 그 단계에서 돌 수 있는 최대 던전의 수를 반환하도록 하였기 때문에 최종적으로 반환하는 값 역시

전체 던전에 대한 최대 던전 레이싱 횟수이다.

 

풀이 코드

def go_dungeons(stamina, count, remainder, dungeons):
    length = len(remainder)
    li = list(remainder)

    if length == 0:
        return count

    next_count = count;
    for i in range(length):
        if stamina >= dungeons[li[i]][0]:
            remainder.remove(li[i])
            next_count = max(next_count, go_dungeons(stamina - dungeons[li[i]][1], count + 1, remainder,dungeons))
            remainder.add(li[i])

    return next_count

def solution(k, dungeons):
    remainder=set([i for i in range(len(dungeons))])


    return go_dungeons(k,0,remainder,dungeons)

 

 

회고

소요시간 50분 초과

재귀함수를 구현하는데 있어서 버벅임이 발생..

종만북 부분 재귀함수 공부 및 정리 필요