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

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

프로그래머스

 

 

1. 해결방법

이 문제에서 완전 탐색 순열을 구현하는 데 떠오른 방법은 두 가지다.
1. dfs를 이용하는 방법
2. 파이썬 itertools라이브러리의 permutations를 이용하는 방법

물론 두 가지 전부 사용해 볼 것이다.

 

 

2. 정답코드

(1) dfs

answer = 0
def solution(k, dungeons):
    
    def enter(i, k):
        global answer
        
        k -= dungeons[i][1]
        answer = max(answer, sum(chk))
        
        for j in range(len(dungeons)):
            if chk[j] == False and k >= dungeons[j][0]:
                chk[j] = True
                enter(j, k)
                chk[j] = False
        
    
    chk = [False] * (len(dungeons))
    for i in range(len(dungeons)):
        if chk[i] == False and k >= dungeons[i][0]:
            chk[i] = True
            enter(i, k)
            chk[i] = False
        
    return answer

본인은 완전 탐색에 대한 알고리즘 능력이 부족해서 이 문제에서도 많이 헤맸다...

중요한 점은 chk[]를 통해서 방문 체크를 해주는 것이고, 모든 던전을 탐색 못하는 경우가 있기에 answer를 도출하기 위해서 chk[]와 sum()메서드를 이용해서 sum(chk)라는 코드를 짜면 방문했던 던전의 합이 구해진다. (chk는 True 또는 False 이다)

본인은 answer 도출하는 것에서 고민을 많이 했다.

 

 

(2) 순열

def solution(k, dungeons):
    from itertools import permutations
    answer = 0
    for perm in permutations(dungeons, len(dungeons)):
        count = 0
        temp_k = k
        
        for p in perm:
            if temp_k >= p[0]:
                count += 1
                temp_k -= p[1]
        answer = max(answer, count)
    
    return answer

순열을 이용하면 간단하게 풀 수 있다. 당연하게도 dfs 방식보다 이해도 잘 된다. 하지만 파이썬 내부 라이브러리인 순열, 중복 순열, 조합이 무엇인지 알아야 이용할 수 있다.

2중 for문을 사용해서 순열을 뽑고, 그 순열 내에서 리스트 하나하나 뽑아서 k 값과 비교한다.