반응형
https://school.programmers.co.kr/learn/courses/30/lessons/87946
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제풀이
(최소 필요 피로도 - 소모 피로도) 의 결과에서 작은 값으로 정렬하고 DP를 적용하여 풀이 할 수 있다.
def solution(k, dungeons):
dp = [0] * (k + 1)
dungeons = sorted(dungeons, key=lambda x: (x[0] - x[1], x[0]))
for dungeon in dungeons:
min_fatigue, consume_fatigue = dungeon
for i in range(k, min_fatigue - 1, -1):
dp[i] = max(dp[i], dp[i - consume_fatigue] + 1)
return dp[k]
처음에는 아래와 같이 접근을 해서 19개의 테스트 케이스에서 3개의 테스트 케이스가 실패가 뜨는것을 보고 최적의 해가 보장 되지 않는다는 것을 확인한 뒤 방법을 바꿔 0/1 Knapsack Problem DP를 적용하게 되었다.
def solution(k, dungeons):
answer = 0
dungeons = sorted(dungeons, key=lambda x: (x[0] - x[1]), reverse=True)
for dungeon in dungeons:
min_fatigue, consume_fatigue = dungeon
if k >= min_fatigue:
k -= consume_fatigue
answer += 1
return answer
