[프로그래머스] 피로도

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

프로그래머스

모든 경우의 수를 확인하면서, 가장 많은 던전을 들어갈 때를 확인하는 문제.

입장 조건이 존재하므로, 순서를 고려하는 기능을 구현하여 확인해야 한다.

 

1. 접근 방법 선택

처음에는 다양한 순서를 고려할 수 있는 DFS로 진행하려고 했으나, 방문 여부 등 추가적으로 넘겨줘야 하는 변수들이 생각나서

너무 많은 수를 넘겨주다보면 메모리 초과가 발생하지 않을까 해서 재귀 함수로 푸는 방법을 선택.

 

2. 문제 해결 시나리오

1번 부터 마지막 던전까지 for 문으로 순회하며, 각 번호의 던전을 가장 처음으로 들어갔을 때를 기점으로

나머지 던전을 순회, 입장 가능여부를 파악하며 계산을 진행한다. 이 때, 나머지 던전을 순회할 때는 직전 방문했던 이력은 없어야 한다.

ex. 최초 진입 던전이 1일 때, 1 -> 2 계산 후 1 -> 3 계산 시, 2번 던전 입장은 안 한 것으로 간주

 

3. 전체 코드

import copy
def check(k, now, info, visited, total):
    need, spend = info[now][0], info[now][1]
    result = 0
    
    if k >= need and k >= spend:
        k -= spend
        visited[now] = 1
        total += 1
        if total == len(info):
            return total
        
        for _next in info:
            if not visited[_next]:     
                result =  max(result, check(k, _next, info, copy.deepcopy(visited), total))
    else:
        return total
        
    return result


def solution(k, dungeons):
    answer = 0
    info = {}
    for idx, d in enumerate(dungeons):
        info[idx] = d
    
    for i in info:
        visited = [0 for _ in range(len(dungeons))]
        answer = max(answer, check(k, i, info, copy.deepcopy(visited), 0))
        
    return answer

함수 check 내부를 보면 3가지 경우를 계산한다.

1. 입장한 던전의 개수가 주어진 던전 정보 개수와 같을 때 > 입장 했던 던전 수 반환

2. 입장 조건 및 남은 피로도가 부족하여 입장을 못할 때 > 현재까지 계산했던 던전 수 반환

3. 입장 조건 및 남은 피로도 조건을 달성하여 입장이 가능할 때 > 1, 2 번 케이스에 도달할 때 까지 반복, 가장 큰 값이 result

4. 최초로 n번 던전 입장 시 최대 입장 가능한 수 반환