프로그래머스 위클리챌린지 12주차 피로도(java)

프로그래머스 위클리챌린지 12주차 피로도(java)

728x90

프로그래머스에서 12주째 하고 있는 위클리 챌린지입니다. 가장 좋아요를 많이 받으면 상품을 준다고 하네요. 저는 그정도 수준은 아닌지라 프로그래머스로 코테 준비도 할 겸 풀어볼 문제가 늘어난다는 것에 만족하면서 문제를 풀고 있습니다. 이제 마지막 주라 풀 시간이 얼마 남지 않았습니다.

이 문제를 풀면서 새삼스레 재귀함수나 경우의 수 관련 문제에서 dfs, bfs를 사용하는데 약점이 있다는 것을 깨닫게 되었습니다. 난이도 자체는 높지 않은 것 같습니다.

피로도

문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

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

dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다. dungeons의 가로(열) 길이는 2 입니다. dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다. "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다. "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다. 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

입출력 예

728x90

kdungeonsresult

80 [[80,20],[50,40],[30,10]] 3

입출력 예 설명

현재 피로도는 80입니다.

만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면

현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.

남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.

남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.

만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면

현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.

남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.

남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.

따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.

여기까지가 문제입니다. 던전의 최대 개수가 8개라서 다른 방식이 아니라 모든 경우의 수를 다 계산해보는 방식을 이용하는 것으로도 충분히 풀 수 있는 간단한 문제입니다.

class Solution { boolean[] isVisit; int max = 0; public int solution(int k, int[][] dungeons) { isVisit = new boolean[dungeons.length]; dungeonCountComputing(dungeons, k, 1); return max; } public void dungeonCountComputing(int[][] dungeons, int k, int depth) { for(int i =0; i< dungeons.length; i++) { if(!isVisit[i]) { isVisit[i] = true; if(k >= dungeons[i][0]) { max = Math.max(max, depth); dungeonCountComputing(dungeons, k - dungeons[i][1], depth+1); } isVisit[i] = false; } } } }

max는 가져갈 수 있는 던전의 최대 개수를 의미합니다. 이는 dungeonCountComputing 메소드를 이용해 구하게 됩니다.

dungeonCountComputing 메소드는 전형적인 dfs의 형식을 따르고 있습니다. isVisit을 통해 방문 상태를 저장하고 반복문을 통해 조건에 맞는 모든 경우의 수를 돌아보게 됩니다. 이때 depth를 통해 몇 번째 던전인지를 파악합니다.

딱히 특별한 코드는 없는 것 같습니다. 그냥 경우의 수를 어떤 방식으로 구하는지에 따라 문제를 풀 수 있게 되는 그런 문제입니다. 하지만 저처럼 이런 부분에 약점을 가지신 분이라면 연습용으로 풀어보기 딱 좋은 그런 느낌의 문제였네요.

728x90

from http://no-dev-nk.tistory.com/56 by ccl(A) rewrite - 2021-10-26 14:27:32