프로그래머스 피로도 python, java

순열을 이용한 방법이다. 던전개수가 8개이므로 가능한 조합 수는 8! 이다.
40320개 가지수이기에 중간에 가지치지를 주지 않아도 전혀 문제가 없다.

📜 문제 바로 가기 : 피로도

제출코드

파이썬

visit = []
dungeons = []
ans = 0

def solution(k, d):
    global visit, dungeons
    
    dungeons = d
    visit = [False] * len(dungeons)
    
    recur(0, k)

    return ans

def recur(s, now):
    global ans
    if s == len(dungeons):
        ans = s
        return
    
    for i in range(len(dungeons)):
        if visit[i] == False and now >= dungeons[i][0]:
            visit[i] = True
            recur(s+1, now - dungeons[i][1])
            visit[i] = False
            
    ans = max(ans, s)

자바

class Solution {
    static int[][] dungeons;
    static boolean[] visit;
    static int ans;
    public int solution(int k, int[][] d) {
        dungeons = d;
        visit = new boolean[d.length];
        
        ans = 0;
        recur(0, k);
        
        return ans;
    }
    
    public void recur(int s, int now) {
        if (s == dungeons.length) {
            ans = s;
            return ;
        }
        
        for (int i = 0; i < dungeons.length; i++) {
            if ((visit[i] == false) && (now >= dungeons[i][0])) {
                visit[i] = true;
                recur(s+1, now - dungeons[i][1]);
                visit[i] = false;
            }
        }
        
        ans = Math.max(ans, s);
    }
}

---

접근방법

나는 조합이나 순열관련 문제를 풀때 재귀함수를 이용하는 것을 좋아한다.
백준에 "N과 M" 시리즈 문제는 조합, 순열에 공부에 많은 도움이 되므로 풀어보는 걸 추천한다!