프로그래머스(Lv.2) - 피로도(Java) (완전탐색)

 위의 문제와 같이 던전의 개수와 최소 피로도, 소모 피로도 등은 정해져 있지만, 어떤 던전을 먼저 가느냐에 따라 클리어할 수 있는 던전 수가 달라진다면, 모든 던전 레이드를 가는 조합을 다 따져봐서 그중 최고만 고르는 방법밖에 없을 것이다.

 

그냥 2중 for문을 통해 던전을 클리어한다면, 순서대로 클리어되기 때문에 2중 for문으로는 모든 조합을 파악해 줄 수 없다. 그래서 Combination을 통해 풀어준다면 모든 조합을 파악해 줄 수 있다.

 

public static void Combination(int lim, int cnt, boolean[] visit, String str)
{
	if(lim == cnt)
	{
		System.out.println(str);
		return;
	}
        
	for(int i = 0 ; i < visit.length ; i++)
	{
		if(!visit[i])
		{
			visit[i] = true;
			Combination(lim, cnt+1, visit, str+Integer.toString(i));
			visit[i] = false;
		}
	}
}

내가 사용한 Combination함수이다. visit[i] = true를 통해 해당 숫자를 썼다는 것을 표시해 주고, 추후 다른 케이스에서 해당 숫자를 다시 써줘야 하니 visit[i] = false를 통해 다시 사용해도 된다는 표시를 해준다면 모든 조합 파악이 가능하다. 이렇게 모든 조합을 뽑아낼 수 있다면, 재귀 부분에 피로도 시스템을 도입해 주면 통과할 수 있다.

<문제>

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

---

<소스코드>

import java.util.*;

class Solution {
    static int ans;
    public int solution(int k, int[][] dungeons) {
        
        Combination(dungeons.length, 0, new boolean[dungeons.length], k, 0, dungeons);
        return ans;
    }
    public static void Combination(int lim, int cnt, boolean[] visit, int tired, int clear, int[][] d)
    {
        if(lim == cnt)
        {
            ans = Math.max(ans, clear);
            return;
        }
        
        for(int i = 0 ; i < visit.length ; i++)
        {
            if(!visit[i])
            {
                visit[i] = true;
                if(tired >= d[i][0])
                {
                    Combination(lim, cnt+1, visit, tired-d[i][1], clear+1, d);
                }
                else
                {
                    Combination(lim, cnt+1, visit, tired, clear, d);
                }
                
                visit[i] = false;
            }
        }
    }
}