[프로그래머스, 파이썬] 피로도

풀이

• 순열 라이브러리를 사용한 풀이와 dfs을 활용한 풀이 두 가지로 해결
• 첫 번째 방법은 순열을 사용해서 모든 경우의 수에 대해 확인하고자 했으며
• 두 번째 방법은 재귀를 활용한 백트래킹을 적용하여 해결
• 두 방법 모두 코드 자체는 단순하여 설명은 패스.

 

첫 번째(순열)

from itertools import permutations

def solution(k, dungeons):

    result = 0    

    for i in list(permutations(dungeons,len(dungeons))):

        pe,cnt = k,0

        for dun in i:

            if pe >= dun[0]:

                pe -= dun[1]

                cnt += 1

        result = max(result,cnt)

    return result

두 번째(dfs)

result = 0

def solution(k, dungeons):

    ln = len(dungeons)

    visit = [0]*ln

    def dfs(val,cnt,check):

        global result

        if check == ln:

            result = max(result,cnt)

        else:

            for i in range(ln):

                if not visit[i]:

                    visit[i] = 1

                    if val >= dungeons[i][0]: dfs(val-dungeons[i][1],cnt+1,check+1)

                    else: dfs(val,cnt,check+1)

                    visit[i] = 0

        return

   

    dfs(k,0,0)

    return result

위 방법처럼 result를 global로 사용하기 좀 애매하다면 아래와 같이 풀이

def solution(k, dungeons):

    ln = len(dungeons)

    result = []

    visit = [0]*ln

    def dfs(val,cnt,check):

        if check == ln:

            result.append(cnt)

        else:

            for i in range(ln):

                if not visit[i]:

                    visit[i] = 1

                    if val >= dungeons[i][0]: dfs(val-dungeons[i][1],cnt+1,check+1)

                    else: dfs(val,cnt,check+1)

                    visit[i] = 0

        return

   

    dfs(k,0,0)

    return max(result)