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

2024년 7월 1일

문제 링크 : 프로그래머스 - 피로도

---

문제 접근

 

규칙을 찾아야하나? 그리디하게 접근해야하나? 한 1분 고민했다. 근데 문제 조건을 보자 일말의 고민도 없이 완전탐색을 해야겠다고 결정했다.

 

던전의 개수는 1 이상 8 이하입니다.

 

문제의 조건을 잘 읽어야 하는 이유이다. N이 작기 때문에 던전을 도는 순서에 대해 모든 경우의 수를 얻어내 각 경우의 수에서 차례대로 던전을 탐험할 때 최대 몇 개까지 탐험할 수 있는지를 모든 경우의 수에서 알아보면 된다.

 

각 경우의 수를 확인하며 최대로 탐험할 수 있는 개수를 계속 갱신시켜주면 된다.

 

나는 모든 경우의 수를 얻어내기 위해 백트래킹 기법을 사용하여 문제를 해결하였다.

---

전체 코드

 

# 던전이 최대 8개이기 때문에 백트래킹으로 모든 경우의 수를 고려해보아도 괜찮겠다고 판단.
def back_tracking(dungeons, dungeons_combi, now_length, max_length, used, k):
    global answer
    
    if now_length == max_length:
        can_explor = 0
        for min_req, cost in dungeons_combi:
            # 최소 필요 피로도 충족
            if k >= min_req:
                k -= cost
                can_explor += 1
            else:
                break
        answer = max(answer, can_explor)
        return

    for i in range(max_length):
        if not used[i]:
            used[i] = True
            dungeons_combi.append(dungeons[i])
            back_tracking(dungeons, dungeons_combi, now_length + 1, max_length, used, k)
            dungeons_combi.pop()
            used[i] = False


def solution(k, dungeons):
    global answer
    answer = 0

    used_dungeons = [False] * (len(dungeons))
    back_tracking(dungeons, [], 0, len(dungeons), used_dungeons, k)    

    return answer


if __name__ == "__main__":
    k = 80
    dungeons = [[80,20],[50,40],[30,10]]

    print(solution(k, dungeons))

---

풀이 후기

 

문제 조건을 읽었을 때 시간복잡도 측면에서 완전탐색이 가능하다면 바로 시도해보는 것이 좋다고 생각한다.

 

때로는 복잡한 문제를 단순하게 접근하였을 때 오히려 적정해를 더 쉽게 구할 수 있다고 생각한다.