[프로그래머스][Python] 피로도, 코드설명

1. 문제링크

코딩테스트 연습 - 피로도 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

2. 코드

from itertools import permutations

def solution(k, dungeons):
    answer = 0
    
    dun_len = len(dungeons)
    
    for permute in permutations(dungeons, dun_len):
        hp = k
        count = 0 
        
        #print(permute)
        
        for pm in permute:
            #print(pm)
            if hp >= pm[0]:
                hp -= pm[1]
                count += 1
            
            if count > answer:
                answer = count
    
    return answer

 

3. 코드 설명

이 문제는 순열을 이용해서 풀었다.

 

3-1 순열이란? (permutation)

서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 말한다.

 

문제를 예시로 쉽게 이해해보자.

dungeons의 값으로 [80,20], [50, 40], [30,10]이 들어오고, k의 값으로 최대 피로도는 80이다.

dungeons[0]은 최소 피로도, dungeons[1]은 사용되는 피로도이다.

최대한 효율적으로 어떤 던전들을 공략할 것인가?가 문제의 핵심이다.

 

dungeons(던전)을 순열로 만들어서 최대한 공략가능한 모든 조합을 찾는다.

그 부분이 for permute in permutation(dungeons, dun_len)이다.

그러면 permute 값으로는

[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] 과 같이 모든 조합을 가지게 된다.

 

 

3-2 순열을 이용한 접근방법

여기서 hp는 최대피로도, count는 돌 수 있는 던전의 수이다.

그리고 던전을 1개씩 돌면서 피로도가 가능한지 확인하기 위해 쪼갠다.

그 부분이 for pm in permute이다.

 

예를 들어 permute 값이 [80,20], [50,40], [30,10]이였다면

pm은 [80, 20] 값을 가지고 for문을 돌면서 각각 값을 얻는다.

 

이 때 hp가 최소피로도 pm[0]보다 크다면 진행시키고 던전을 돈 것이므로 count를 올려준다.

그리고 answer보다 크다면 answer 값을 갱신시키고 제일 높은 answer 값을 리턴해준다.