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

#12주차 피로도

유형 : 완전탐색/ 조합/ DFS

코딩테스트 연습 - 피로도

▸ 문제

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

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

▸ 제한사항

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

 

문제 풀이  

처음에 그리디로 접근했다가 최소 필요 피로도가 높다고 소모 피로도가 높은 것도 아니기 때문에 적절한 탐욕 선택 방식을 찾지 못했다.

 

그래서 dungeons의 최대 크기가 8이기 때문에 모든 경우의 수를 구해 탐색하는 브루트포스한 방식을 선택했다. 기본적인 구현 방법으로 1~dungeons의 수만큼 조합을 모두 구한 다음 직접 대입해보며 유저가 탐험할 수 있는 최대 던전 수를 카운팅을 해주도록 설계했다.

 

설계

1. (1~dungeons의 수)의 경우의 수를 모두 구한다. comb(n);
2. 브루트포스하게 구한 경우의 수 순서대로 던전을 탐험해보며 던전 수를 카운팅한다. simulation(list);
3. 최대로 탐험할 수 있는 최대 던전 수를 출력해준다. return max;

 

풀이 코드 

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class Solution {
    static int f, max=-1;
    static int[][] data;
    static boolean[] check;
    static Stack<Integer> s;
    public int solution(int k, int[][] dungeons) {
        f = k;
        data = dungeons.clone();
        int n = dungeons.length;
        s = new Stack<>();
        check = new boolean[n+1];
        comb(n);
        return max;
    }

    static void comb(int r) {
        if(s.size() == r) {
            List<Integer> list = new ArrayList<>();
            for(int num : s) {
                list.add(num-1);
            }
            simulation(list);
            return;
        }
        for(int i=1; i<=r; i++) {
            if(!check[i]) {
                check[i] = true;
                s.push(i);
                comb(r);
                s.pop();
                check[i] =false;
            }
        }
    }

    static void simulation(List<Integer> list) {
        int cnt=0;
        int fatigue = f;
        for(int order : list) {
            if(fatigue>= data[order][0]) {
                fatigue-= data[order][1];
                cnt++;
            }
        }
        max = Math.max(max, cnt);
    }
}

 

DFS 풀이 코드

위의 풀이를 하고 다른 풀이를 참고하니 DFS탐색으로 재귀호출 방식으로 사용하여 풀이를 한 것을 보고 한수 배웠다. 굳이 모든 조합의 수를 구한 다음 대입할 과정을 거칠 필요없이 그냥 직접 재귀탐색으로 경로를 탐색해주면 알아서 모든 조합을 거치기 때문에 간단하게 답을 구할 수 있다.

class Solution {
    public int solution(int k, int[][] dungeons) {
        return dfs(k,dungeons);
    }
	
	static int dfs(int k, int[][] dungeons) {
		int cnt=0;
		for(int[] d : dungeons) {
			int a = d[0];
			if(k>=d[0]) {
				d[0] = 5001;
				cnt = Math.max(1+dfs(k-d[1],dungeons), cnt);
				d[0] = a;
			}
		}
		return cnt;
	}
}