[완전탐색] 프로그래머스 피로도(python)

 

 

 

 

 

 

안녕하세요

---

문제

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

최종코드

from itertools import permutations

def solution(k, dungeons):
    randomList = permutations(dungeons, len(dungeons))
    count = 0
    k2 = k
    
    for random in randomList:
        c = 0; k2 = k
        for r in random:
            if k2<r[0]: continue
            c+=1
            k2-=r[1]
    
        count = c if c>count else count
        
    return count

 

 파이썬 순열 라이브러리 이용해서 풀었습니다. 이 문제가 정확도만 요구해서 넘어간 것 같고, 만약 효율성도 있었으면 나가리였을 겁니다. 

 

# 조합: 중복을 허용하지않고, 뽑은 순서를 고려하지 않음
from itertools import combinations
combinations(items, 2) # items는 반복 가능한 자료형(리스트 등)이어야 함

# 순열: 중복을 허용하지 않고, 뽑힌 순서대로 나열
# 같은 값이 뽑히더라도 순서가 다르면 다른 경우의 수로 취급함)
from itertools import permutations
permutations(items, 2)

# 둘 다 결과물은 튜플

 

 조합과 순열의 차이점을 아시겠나요? 순열은 조합한 순서가 다른면 다른 경우로 인식하지만, 조합은 그렇지 않습니다. 이 문제는 유저의 현재 피로도 K를 상정했을 때, 가장 많이 돌 수 있는 던전의 수를 구하는 문제입니다. 따라서, 던전 별로 요구하는 최소 피로도와 소모 피로도의 순서가 중요하죠. 그래서 순열을 사용했습니다. 

 

---

기타

 푸는데는 10분도 안 걸린 것 같습니다. <완전탐색>이라는 키워드를 알아서 빨린 푼 것 같습니다. 

 

1. 처음에 최소 소모도가 크고 소모 피로도가 작은 순으로 정렬할까도 생각했는데, 예제를 보면 꼭 그렇진 않아서 바로 폐기함. <정렬> 파트도 아님
2. 초반에 k2 초기화하는 거 까먹고 쌩 k를 for문 돌렸는데. 테케 통과하길래 제출했더니 7개가 오류 나길래 뭔 지 보느라 시간 좀 더 걸림

---

끗