프로그래머스 - 피로도

lv. 2 단계의 코딩 테스트 연습 문제 중 '피로도'에 대한 풀이를 설명하고 있습니다.

 

프로그래머스 - 피로도

 

코딩 테스트 연습 문제 풀이

 

1. 원리

2. 코드

추천글

위의 목차를 클릭하면 해당 글로 자동 이동 합니다.

 

원리

• 이 문제도 마찬가지로 DFS를 활용하면 된다.
• 그런데 계산을 계속 하면서 DFS를 하기 보다는 순열을 만들면 된다.
• 모르고 변수 이름을 comb로 지었는데 perm로 생각하는 게 좋을 것 같다...
• 던전의 고유 인덱스를 기준으로 중복없이 하나씩 담는다.
• 그러고 나서 던전 갯수만큼 담는 것이 완료되면, 담긴 순서대로 던전을 하나씩 돌아본다.
• 그렇게 해서 몇 개의 던전을 돌 수 있는지 센다.
• 이렇게 만들어질 수 있는 순열들에 대해 모두 계산해보고 가장 큰 경우를 저장하면 된다.
• dfs() 그리고 cntDungeons() 로 메소드를 구분해놓았다.
• 전역 변수를 적절히 활용했다.

코드

from collections import deque

def cntDungeons():
    global comb, K, D
    k = K
    cnt = 0
    for i in comb:
        if D[i][0] <= k:
            k -= D[i][1]
            cnt += 1
        else:
            break
    return cnt
    

def dfs(depth):
    global N, comb, answer
    if depth == N:
        answer = max(answer, cntDungeons())
    else:
        for i in range(N):
            if i not in comb:
                comb.append(i)
                dfs(depth + 1)
                comb.pop()
    
def solution(k, dungeons):
    global answer, N, K, D
    D = dungeons
    N = len(dungeons)
    K = k
    dfs(0)
    return answer

N = -1
K = -1
D = []
answer = 0
comb = deque()

 

DFS를 좀 더 쉽게 짜고 싶다. 특히 BFS와 같이 깔끔한 코드와 달리 나는 전역 변수도 섞어 쓰니까 지저분한 것 같다..

 

추천글

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

프로그래머스