[프로그래머스] 피로도 (파이썬)

🗓️ 문제 설명

• XX게임에는 피로도 시스템(0 이상의 정수로 표현)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다.
• 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다.
• "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다.
• 이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다.
• 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons가 매개변수로 주어질 때, 유저가 탐험할 수 있는 최대 던전 수를 반환해주세요.
• 제한 사항
  • k는 1 이상 5,000 이하인 자연수
  • dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하
    • dungeons의 가로(열) 길이 = 2
    • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"]
    • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같음
    • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수
    • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있음
• 입출력 예시

k	dungeons	result
80	[[80, 20], [50, 40], [30, 10]]	3

 

💻 코드

최종 코드

• 수정사항
  >> 반복문의 range를 dungeons의 길이 대신 순열 p의 길이 사용

 

코드 풀이

 

다른 사람 풀이

풀이 1번

1. 1 ~ 3번줄 : 글로벌 변수 및 리스트 생성
2. 6번줄 : "현재 피로도", 변수, dungeons를 매개변수로 받는 dfs 함수 생성
   1. 7번줄 : 글로벌 변수 answer를 불러옴
   2. 8 ~ 9번줄 : cnt가 answer보다 크다면 answer에 cnt를 저장
   3. 11번줄 : N만큼 반복되는 반복문 실행
      1. 12번줄 : dungeons의 j번째 "최소 필요 피로도"보다 현재 피로도가 크거나 같고, visited의 j번째 값이 0인지 확인하는 조건문 실행
      2. 13번줄 : 조건문이 참이라면 visited의 j번째 값에 1을 저장
      3. 14번줄 : "현재 피로도"에서 "소모 피로도"를 뺀 값, cnt+1, dungeons를 매개변수로 dfs 함수를 재귀적으로 실행
      4. 15번줄 : visited의 j번째 값에 0을 저장
3. 19번줄 : 글로벌 변수 N, 글로벌 리스트 visited를 불러옴
4. 20번줄 : N에 dungeons의 길이를 저장
5. 21번줄 : N의 길이만큼 [0]인 리스트를 visited에 저장
6. 22번줄 : "현재 피로도", 0, dungeons를 매개변수로 dfs 함수 실행 

 

⚙️ 시행착오

1차 시도

• 테스트 결과 : 19개 중 8개 실패