프로그래머스

[프로그래머스][LV.2] 피로도 | python3

발자개a 2025. 3. 14. 17:10

문제링크:  피로도

문제설명

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

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

 

제한조건

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

 

문제풀이

순열조합을 활용하여 던전의 순서를 모두 구한다.

from itertools import permutations 로 임포트 하여 순열조합을 사용.

 

permutations(반복가능한객체,r)

=>반복가능한객체에서 r개의 순서있는 조합

 

던전의 모든 순서를 구한 후 루프문을 돈다.

한 순서조합당 갈 수 있는 던전의 갯수를 구한 후 그 전의 갯수와 비교하여 더 큰값을 가지고 옴.

 

나의코드

from itertools import permutations

def solution(k, dungeons):
    # 그 순열 조합으로 던전의 조합을 찾고 루프문 돌려서 가장 많이 탐험할 수 있는 (max) 수를 구하면 되나..
    # 던전 수가 최대 8개이면...시간 복잡도가 괜찮나?
    total_dungeans=permutations(dungeons,len(dungeons))
    answer=-1
    for dungeans in total_dungeans:
        cnt=0
        n=k
        for m,s in dungeans:
            if n>=m:
                n-=s
                cnt+=1
        answer=max(answer,cnt)
    return answer

 

 

더보기

참고하기

# 탐험할 수 있는 최대 던전 개수를 저장하는 변수
answer = 0  # 던전의 개수를 저장하는 변수
N = 0   # 던전 방문 여부를 저장하는 리스트
visited = []  


def dfs(k, cnt, dungeons):
    """
    DFS를 사용하여 모든 가능한 던전 탐험 경로를 탐색하는 함수
    :param k: 현재 남은 체력
    :param cnt: 현재까지 탐험한 던전 개수
    :param dungeons: 던전 리스트 (최소 필요 체력, 소모 체력)
    """
    global answer
    
    # 현재 탐험한 던전 개수가 최대값보다 크면 갱신
    if cnt > answer:  
        answer = cnt  

    # 모든 던전을 탐색
    for j in range(N):
        # 현재 체력이 최소 필요 체력 이상이고, 방문하지 않은 경우 탐험 가능
        if k >= dungeons[j][0] and not visited[j]:  
            visited[j] = 1  # 방문 처리
            dfs(k - dungeons[j][1], cnt + 1, dungeons)  # 체력을 소모하고 다음 탐색 진행
            visited[j] = 0  # 백트래킹 (다른 경로도 탐색할 수 있도록 방문 해제)


def solution(k, dungeons):
    """
    최대한 많은 던전을 탐험할 수 있는 개수를 구하는 함수
    :param k: 초기 체력
    :param dungeons: 던전 리스트 (최소 필요 체력, 소모 체력)
    :return: 탐험할 수 있는 최대 던전 개수
    """
    global N, visited
    N = len(dungeons)  # 던전 개수 저장
    visited = [0] * N  # 모든 던전을 미방문 상태로 초기화
    dfs(k, 0, dungeons)  # DFS 탐색 시작
    return answer  # 탐험할 수 있는 최대 던전 개수 반환

 DFS 접근법...

재귀함수를 이용한 풀이인데 이해가 될 듯 말듯....

 

def solution(k, dungeons):
    answer = 0
    dungeons = sorted(dungeons, key = lambda x : ((x[1]+x[0])/x[0],x[1]))
    for x,y in dungeons:
        print("x :", x, "y : ", y)
        if k >= x:
            k -= y
            answer += 1
    return answer

 

solution = lambda k, d: max([solution(k - u, d[:i] + d[i+1:]) + 1 for i, (m, u) in enumerate(d) if k >= m] or [0])

이 람다 함수는 재귀 호출을 이용해 모든 가능한 던전 탐험 경로를 탐색하고, 탐험할 수 있는 최대 던전 개수를 반환하는 방식

📌 코드 동작 순서

solution = lambda k, d: max([solution(k - u, d[:i] + d[i+1:]) + 1 for i, (m, u) in enumerate(d) if k >= m] or [0])

🔹 1. 가능한 던전 찾기 (for 루프)

for i, (m, u) in enumerate(d) if k >= m
  • enumerate(d)를 사용해 던전 리스트 d를 인덱스 i와 (최소 필요 체력 m, 소모 체력 u)로 분해
  • if k >= m → 현재 체력 k로 탐험할 수 있는 던전만 필터링

🔹 2. 탐험 가능한 던전에 대해 재귀 호출 (solution(k - u, ...))

solution(k - u, d[:i] + d[i+1:]) + 1
  • 현재 던전 i를 선택하면 체력 k에서 소모 체력 u를 뺀 값으로 재귀 호출
  • d[:i] + d[i+1:] → 현재 탐험한 던전 i를 제외한 나머지 던전 리스트를 새로운 d로 설정
  • +1 → 현재 던전을 탐험했으므로 개수 증가

🔹 3. 모든 경우 중 최대 탐험 개수 선택 (max([...]))

max([...])
  • 탐험 가능한 모든 경우를 고려하여 최대 탐험 개수를 선택

🔹 4. 탐험할 수 있는 던전이 없을 때 (or [0])

or [0]
  • 던전을 탐험할 수 있는 경우가 하나도 없으면 리스트가 []가 되므로 max([])는 오류 발생
  • 이를 방지하기 위해 최소값 [0]을 넣어 탐험하지 못한 경우 0을 반환