1. 문제 설명
어떤 게임은 일정 피로도를 사용하여 던전을 탐험할 수 있다.
이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있다.
- 최소 필요 피로도 : 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도
- 소모 피로도 : 던전을 탐험한 후 소모되는 피로도
예를 들어 '최소 필요 피로도'가 80, '소모 피로도'가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모된다.
하루에 한 번씩 탐험할 수 있는 던전이 있을 때, 한 유저가 오늘 최대한 많이 탐험하려고 할 때, 유저가 탐험할 수 있는 최대 던전 수를 반환하라.
2. 제한 사항
- k는 1 이상 5,000 이하인 자연수
- dungeons의 각 행은 각 던전의 ['최소 필요 피로도', '소모 피로도'] 이다.
3. 코드
(1) 완전 탐색 - DFS
answer = 0
def explore(power, cnt, is_visited, dungeons):
global answer
if cnt > answer:
answer = cnt
for i in range(len(dungeons)):
if power >= dungeons[i][0] and is_visited[i] == False:
is_visited[i] = True
explore(power - dungeons[i][1], cnt + 1, is_visited, dungeons)
is_visited[i] = False
def solution(k, dungeons):
global answer
is_visited = [ False for _ in range(len(dungeons)) ]
explore(k, 0, is_visited, dungeons)
return answer
(2) 순열
from itertools import permutations
def solution(k, dungeons):
answer = 0
for pemutation in permutations(dungeons, len(dungeons)):
power = k
cnt = 0
for need, spend in permutation:
if power >= need:
power -= spend
cnt += 1
else:
break
answer = max(answer, cnt)
return answer
4. 해설
(1) 완전 탐색 - DFS
깊이 우선 탐색 방식으로 모든 경우를 따져준다.
전역 변수 answer를 선언하여, 던전의 최대 탐험 개수를 갱신했을 때 answer 값을 바꿔준다.
이미 지나온 던전인지를 저장하는 is_visited 배열을 만들어주고 DFS를 수행하는 함수인 explore를 호출한다.
explore 함수는
- 전역 변수 answer보다 탐험한 던전의 개수가 더 많을 경우 갱신을 해준다.
- 던전의 경우를 for문으로 모두 검토하면서 방문하지 않았는지, 방문할 수 있는지 (최소 필요 피로도를 만족하는지) 확인하여 재귀적 호출을 진행한다.
- 핵심은 호출 이후로 is_visited[i] = False로 만들어주어, 다음 경우에는 다시 방문할 수 있도록 하는 것이다.
(2) 순열
from itertools import permutations를 통해서 가능한 모든 경우의 수를 구한다.
- for permutation in permutations(dungeons, len(dungeons))
예시 :
([80, 20], [50, 40], [30, 10])
([80, 20], [30, 10], [50, 40])
([50, 40], [80, 20], [30, 10])
([50, 40], [30, 10], [80, 20])
([30, 10], [80, 20], [50, 40])
([30, 10], [50, 40], [80, 20]))
'Algorithm' 카테고리의 다른 글
프로그래머스 > 전화번호 목록 (Python 3) (0) | 2024.07.09 |
---|---|
프로그래머스 > 뉴스 클러스터링 (Python 3) | Counter, 다중 집합 (0) | 2024.07.08 |
프로그래머스 > 튜플 (Python3) (0) | 2024.07.07 |
프로그래머스 > [1차] 캐시 (Python3) (0) | 2024.07.04 |
프로그래머스 > 의상 (Python3) (0) | 2024.07.03 |