[프로그래머스 / Java] Lv.2 피로도 - 연습 문제 (1) with ChatGPT (업데이트 중..)

📘 연습 문제  : 배터리로 미션 최대 수행

 

문제 설명

로봇은 현재 배터리 b를 가지고 있고, 여러 개의 미션이 있습니다.
각 미션은 다음 정보를 가집니다.

• missions[i][0] : 해당 미션을 시작하기 위한 최소 배터리
• missions[i][1] : 미션 수행 후 소모되는 배터리

로봇은 미션을 한 번씩만 수행할 수 있으며, 수행 순서는 자유입니다.
수행할 수 있는 미션의 최대 개수를 구하세요.

 

💡입력

• 정수 b (초기 배터리)
• 2차원 배열 missions

💡출력

• 수행 가능한 미션의 최대 개수

---

예시

 

 

---

Algorithm

1.  

---

Code

class Solution {

    static int answer = 0;
    static boolean[] visited;

    public int solution(int b, int[][] missions) {
        visited = new boolean[missions.length];
        dfs(b, missions, 0);
        return answer;
    }

    private void dfs(int battery, int[][] missions, int done) {
        // 최대 수행 개수 갱신
        answer = Math.max(answer, done);

        // 다음에 수행할 미션 선택
        for (int i = 0; i < missions.length; i++) {
            int need = missions[i][0];   // 최소 필요 배터리
            int cost = missions[i][1];   // 소모 배터리

            // 아직 안 했고, 시작 조건을 만족하면 수행
            if (!visited[i] && battery >= need) {
                visited[i] = true; // 방문 처리
                dfs(battery - cost, missions, done + 1); // 다음 단계
                visited[i] = false; // 백트래킹
            }
        }
    }
}

 

---

문제 링크

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

프로그래머스