[프로그래머스] 피로도

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/87946

코딩테스트 연습 - 12주차

 

프로그래머스 위클리 챌린지 마지막 문제입니다.

문제의 난이도가 일정하지 않은 점이나, 작성된 코드가 노출되어 좋아요를 받는 방식, 예전에 본 듯한 문제들 등이 좀 아쉽긴 했지만 이렇게 위클리 챌린지가 종료된다고 하니 이것도 아쉽네요.

 

문제 조건을 요약하면 다음과 같습니다.

• 맨 처음 주어진 피로도가 있다. 피로도는 던전을 접근할 때마다 감소한다.
• 각 던전에는 요구 피로도와 소모 피로도가 있다. 요구 피로도는 던전을 접근하기 위해 필요한 피로도의 최소 수치이며, 소모 피로도는 해당 던전을 접근할 경우 그 수치만큼 나의 피로도가 감소한다.
• 던전은 최소 1개, 최대 8개까지 존재한다.

 

던전의 개수가 매우 작은 만큼, 완전탐색을 하기에 어렵지 않습니다.

저는 재귀함수를 이용한 DFS식 완전탐색을 수행하였고, 탐색이 종료될 때마다 접근한 던전의 수를 구하고, 그 최댓값을 매번 갱신하여 정답으로 반환하였습니다.

 

 

채점 결과

데이터의 개수 제한과 조건을 생각해 본다면 완전 탐색을 어렵지 않게 떠올릴 수 있었습니다.

완전탐색 외에 처음에 떠오를 법한 방법은 그리디 혹은 DP인데, 요구 피로도와 소모 피로도가 별개의 값인 만큼 이 두 방법으로의 접근은 쉽지 않은 것 같습니다.