[프로그래머스/Lv2] 피로도

문제

XX게임에는 피로도 시스템(0 이상의 정수로 표현)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있다.

이때, 각 던전마다 탐험을 시작하기 위해 필요한 '최소 필요 피로도'와 던전 탐험을 마쳤을 때 소모되는 '소모 피로도'가 있다.

'최소 필요 피로도'는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며,

'소모 피로도'는 던전을 탐험한 후 소모되는 피로도를 나타낸다.

 

예를 들어 '최소 필요 피로도'가 80, '소모 피로도'가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모된다.

 

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 한다.

유저의 현재 피로도 k와 각 던전별 '최소 필요 피로도', '소모 피로도'가 담긴 2차원 배열 dungeons가 매개변수로 주어질 때, 유저가 탐험할 수 있는 최대 던전 수를 반환하는 함수를 만들어야 한다.

 

 

제한사항

1. k는 1 이상 5,000 이하인 자연수이다.

2. dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하이다.

   -> dungeons의 가로(열) 길이는 2 이다.

   -> dungeons의 각 행은 각 던전의 ['최소 필요 피로도', '소모 피로도']이다.

   -> '최소 필요 피로도'는 항상 '소모 피로도'보다 크거나 같다.

   -> '최소 필요 피로도'와 '소모 피로도'는 1 이상 1,000 이하인 자연수이다.

   -> 서로 다른 던전의 ['최소 필요 피로도', '소모 피로도']가 서로 같을 수 있다.

 

 

코드 

from itertools import permutations

def solution(k, dungeons):
    cases = list(permutations(dungeons, len(dungeons)))
    max = 0
    for case in cases:
        check = 0
        fatigue = k
        for dungeon in case:
            if fatigue < dungeon[0]:
                break
            else:
                fatigue -= dungeon[1]
                check += 1
        
        if check > max:
            max = check

    return max

 

 

설명

문제 제출을 해보면 효율성은 따지지 않는 문제라는 것을 알 수 있다.

던전을 탐험하는 모든 경우의 수를 따져서 가장 많이 탐험할 수 있는 횟수를 알아내 반환하면 통과된다.

 

from itertools import permutations

cases = list(permutations(dungeons, len(dungeons)))

순열을 이용해서 dungeons의 길이만큼 원소들을 골라 나열한다.

나열한 것들을 cases에 저장한다.

 

max = 0
for case in cases:
    check = 0
    fatigue = k
    for dungeon in case:
        if fatigue < dungeon[0]:
            break
        else:
            fatigue -= dungeon[1]
            check += 1

    if check > max:
        max = check

max는 탐험할 수 있는 최대 던전의 수를 기록하는 변수이다.

cases의  원소(case)들을 꺼내며 반복한다.

check는 현재 case에서의 탐험할 수 있는 던전 수를 기록하는 변수이다.

fatigue는 피로도를 의미한다.

 

case의 원소(dungeon)을 꺼내며 반복한다.

만약 현재 fatigue가 dungeon의 첫번째 원소(최소 필요 피로도)보다 작다면 반복을 강제 종료한다.

그렇지 않다면 fatigue에 dungeon의 두번째 원소(소모 피로도)만큼을 빼고 check를 1 더해준다.

 

안쪽 반복이 끝나면

check와 max를 비교하여 큰 값을 max에 저장한다.

 

return max

모든 반복이 끝나면 구해진 max를 반환한다.