프로그래머스 : 피로도 (Java)

🔗 문제 링크

코딩테스트 연습 - 피로도

---

📖 풀이 과정

- 재귀를 이용한 완전탐색 유형의 문제입니다.

- visited라는 boolean 1차원 배열을 선언했습니다.

  - 크기는 dungeons의 길이로 선언하면 됩니다.
  
- 조건은 2가지 입니다.

  - 이전에 방문하지 않은 곳이어야 합니다.
  
  - 현재 피로도가, 최소 필요 필요도 이상이어야 합니다.
  
- 이 두가지 조건을 유지한채 재귀로 완전탐색을 실시합니다.

- 모든 구현이 마치면, count 변수와 answer 변수를 비교하여 최대값을 반환합니다.

---

💻 코드

class Solution {
    static boolean[] visited;
	static int answer = 0;
    
	public static int solution(int k, int[][] dungeons) {
		visited = new boolean[dungeons.length];
		
		return solve(dungeons,k,visited,0);
	}
	
	private static int solve(int[][] dungeons, int k, boolean[] visited, int count){
		for(int i = 0; i < dungeons.length; i++){
			if(k >= dungeons[i][0] && !visited[i]){
				visited[i] = true;
				solve(dungeons,k - dungeons[i][1], visited, count + 1);
				visited[i] = false;
			}
		}
		answer = Math.max(answer, count);
		
		return answer;
	}
}