[Programmers] 피로도 - Java

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

프로그래머스

---

 

1. 문제

현재 피로도 k, 던전 이차원 배열([0]: 최소 필요 피로도, [1]: 소모 피로도)이 주어졌을 때

유저가 탐험할 수 있는 최대 던전 수이다.

던전 배열의 첫번째 요소가 예를 들어 [80,20]일 경우, 첫번째 던전에 입장하는데 필요한 최소 피로도는 80, 입장 후 소모되는 피로도는 20인 것이다.

 

2. 풀이

순열 문제이다.

던전의 순서를 순열로 줄세워 가장 많이 입장할 수 있는 max 값을 갱신하여 답을 구했다.

1. 순열 함수 들어오자마자 max와 cnt값을 비교하여 max를 갱신해주었다. 여기서 cnt는 던전 입장 횟수이다.

2. 유효성 검사 후 피로도가 최소필요피로도보다 작거나, 소모될 피로도보다 작을 경우 continue로 보지않았다.

3. 다음 순서로 넘어간다.

 

순열은 비트마스킹으로 풀었다.

비트마스킹을 쓰면 사용여부를 flag로만 체크하고 isVisited나 isSelected와 같이 자료구조를 만들지 않고도 손쉽게 유효성검사를 할 수 있어서 편한 것 같다.

 

3. 코드

class Solution {
    
    static int max, length, dungeon[][];
    
    public int solution(int k, int[][] dungeons) {
        dungeon = dungeons;
        length = dungeons.length;
        
        perm(0, 0, 0, k);
        
        return max;
    }
    
    static void perm(int idx, int cnt, int flag, int hp) {
        max = Math.max(max, cnt);
        if (idx == length) {
            return;
        }
        for (int i=0; i<length; i++) {
            if ((flag & (1<<i)) != 0) continue;
            if (hp < dungeon[i][0] || hp < dungeon[i][1]) continue;
            perm(idx+1, cnt+1, flag|(1<<i), hp-dungeon[i][1]);
        }
    }
}

 

4. 사담

비트마스킹을 왜 이제야 알았을까 꽤나 편한듯