[JAVA] 프로그래머스 - 피로도

문제내용

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

코딩테스트 연습 - 피로도

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

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

제한사항

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

입출력 예

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입니다.

---

문제 풀이

던전이 총 n개가 있을때 r개의 던전을 뽑아서 탐험시키면되는 문제이다. 즉, 백트래킹을 이용한 조합으로 풀어내면 풀리는 문제인데 다만, 주어진 피로도 내에서 탐험 가능한 던전들만 뽑아서 탐험해야한다는 조건을 추가시켜주면 된다.

 

로직

첫번째: 던전을 중복해서 탐험하지 않도록 방문배열 생성한다.

두번째: 방문했던 던전이거나 현재 피로도가 탐험하려는 던전의 최소 피로도보다 낮다면 다음으로 넘어간다.(추가조건)

세번째: 특별한 종료조건없이 시작부터 던전을 하나 방문할때마다 방문했던 던전의 개수를 세고, 최대값으로 갱신한다.

 

결론적으로 두번째와 세번째를 반복해주면 답이나온다.

---

코드

public class Solution {
	static private boolean[] check;//방문배열
	static private int res;//결과값
    
	public static int solution(int k, int[][] dungeons) {
		int dCnt = dungeons.length;//던전 개수
		res = Integer.MIN_VALUE;//초기화
		check = new boolean[dCnt];//초기화
		back(k,dungeons);//던전 탐험 시작.
		
		return res;
	}
	
	//back(현재 피로도, 던전배열)
	public static void back(int piro, int[][] dungeon) {
		dungeonCnt();//탐험한 던전 개수 세기.
		
		for(int i=0; i<check.length; i++) {
			if(check[i]) continue;//방문했었으면 다음 던전으로
			if(piro<dungeon[i][0]) continue;//현재 피로도보다 던전의 최소 피로도가 높으면 다음 던전으로
				check[i]=true;//방문
				back(piro-dungeon[i][1], dungeon);//현재 피로도에서 지금 방문한 던전의 소모 피로도를 빼고 재귀.
				check[i]=false;//되돌리기
		}
	}
	
	public static void dungeonCnt() {
		int cnt = 0;
		for(int i=0; i<check.length; i++) 
			if(check[i]) cnt++;
		
		res = Math.max(res, cnt);
	}
}

---

마치며

일반적인 백트래킹처럼 종료조건이 따로 있는건 아니라서 재귀를 할때 마다 매번 탐험한 던전의 개수를 세야하는 단점이 있는 코드이다. 이게 가능할수 있는 이유는 주어진 던전의 개수가 최대 8개 밖에 안되기때문...

어쨌든 주어진 입력의 범위가 작을땐 이렇게 코드를 짤 수 있다는것도 알아두자.