[Python] 프로그래머스 lv.2 피로도

 

문제 분석

• 피로도 시스템 (0이상의 정수)
• 일정 피로도를 사용해서 던전 탐험을 할 수 있다.
• 각 던전마다 탐험을 시작하기 위해 갖고 있어야 하는 최소한의 필요도 : "최소 필요 피로도"
• 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"
• 하루에 한 번씩 탐험할 수 있는 던전 여러개 
• 한 유저가 오늘 던전들을 최대한 많이 탐험하려 한다.
• 유저의 현재 피로도 k와
• 각 던전별 '최소 필요 피로도(min_b)'와 '소모 피로도(consume_b)'가 담긴 2차원 배열 dungeons가 주어짐
• 유저가 탐험할 수 있는 최대 던전 수를  return

 

코드 설계

• 완탐으로 코드를 설계한다면 dungeons의 1차원 배열 개수만큼 순열을 구하고
• 해당 순열만큼 다 돌았을 때의 돈 던전의 최대 수 return 

 

정답 코드

1차 - 성공

from itertools import permutations

def solution(k, dungeons):
    answer = []
    num = [i for i in range(len(dungeons))] # 던전도는 모든 경우의 수의 순열을 만들기 위한 리스트
    n = 0
    origin_k = k # k를 다시 원래대로 되돌리기 위해 초기값 저장
    
    for seq in permutations(num, len(dungeons)):
        seq = list(seq) # 던전을 도는 모든 순서
        k = origin_k # 해당 순서에 따른 던전을 돌 수 있는 순서를 구하기 전에 k 초기값으로 되돌리기
        answer.append(0)
        for i in seq:
            if k >= dungeons[i][0] :
                answer[n] += 1
                k -= dungeons[i][1]
        n += 1

    print(answer)
    return max(answer)

 

다른 사람 코드 1

answer = 0
N = 0
visited = []


def dfs(k, cnt, 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):
    global N, visited
    N = len(dungeons)
    visited = [0] * N
    dfs(k, 0, dungeons)
    return answer

 

다른 사람 코드 2

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

• 던전 리스트를 특정 비율로 정렬
  • 기준 1 : x[1] + x[0] / x[0]
    • 던전이 소모되는 체력 x[1]을 필요 체력 x[0] 에 대한 비율로 정렬
  • 기준 2 : x[1]
    • 소모되는 체력을 기준으로 정렬
• 정렬 : [[80, 20], [50, 40], [30, 10]]  → [[80, 20], [30, 10], [50, 40]]

위와 같이 정렬하여 던전의 수를 최대화 함

 

다른 사람 코드 3

from itertools import permutations
def solution(k, dungeons):
    answer = 0
    n = len(dungeons)
    for order in permutations(range(n)):
        #print(t)
        cur = k
        local_ans = 0
        for t in order:
            require, consum = dungeons[t]
            if cur >= require:
                cur -= consum
                local_ans += 1
        answer = max(answer, local_ans)
    return answer