[프로그래머스] 피로도 (Python)

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

코딩테스트 연습 - 피로도

 

그리디 + 완전 탐색으로 풀었다.

던전 총개수를 세고,

최대 던전 개수부터 내려오면서 순열을 만든 다음

모두 탐색하며 조건에 만족하면 바로 return 하도록 코드를 작성했다.

 

나의 풀이

from itertools import permutations
def solution(k, dungeons):
    dungeons_count = len(dungeons)
    dungeons_list = [i for i in range(dungeons_count)]
    for i in range(dungeons_count,0,-1):
        for cases in permutations(dungeons_list,i):
            now = k
            check = True
            for case in cases:
                if now < dungeons[case][0]:
                    check = False
                    break
                else:
                    now -= dungeons[case][1]
            if check:
                return i

 

다른 사람 풀이

 

dfs 로 풀어보고 싶었는데 도저히 생각이 안 나서 고민했는데, 이 사람 방식대로 풀면 된다.

visited 설정 해주고 dfs 부른 다음 다시 visited[j] = 0으로 해서 모든 경우를 따지도록 계산했다.

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