[프로그래머스] 피로도

피로도

https://campus.programmers.co.kr/tryouts/140902/challenges

 

 

문제 파악

💡 -dfs, bfs, dp로도 풀 수 있는 문제

-가진 체력으로 각 던전을 돌며 최대 던전 돌 수 있는 횟수 구하기

-똑같은 게 계속 반복된다. ⇒ 작은 문제로 줄여서 풀기 (재귀)

-순차적으로 돌 필요 없고 어떤 조합이든 많이 돌 수 있는 방법 찾기.

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

 

접근 방법

-각 던전에 주어진 행은 같으므로 해당 행을 도는 recursive call을 작성 (최소 단위)

-수도 코드

public class 피로도 {
    public int solution(int k, int[][] dungeons) {
        int answer = -1;
        return answer;
    }
    public void backtrack(int k, int[][] dungeons) {
        //base case
        if( 필요피로도 >k){
            answer = max();
            return;
        }
        //recursive call
        for (int row = 0; row < dungeons.length; row++) {
            dungeons[i] 추가하기
            backtrack();
            dungeons[i] 빼기    
        }
        
    }
}

코드 구현

import java.util.*;
public class Solution {
    int answer=0;
    public int solution(int k, int[][] dungeons) {
        int n = dungeons.length;
        boolean[] visited = new boolean[n];
        backtrack(n,k,0,dungeons,visited);
        
        return answer;
    }
    public void backtrack(int n,int k,int cnt,int[][] dungeons,boolean[] visited) {
        if(answer<cnt) answer = cnt;
        //recursive call
        for(int i=0;i<n;i++){
            if(dungeons[i][0]<=k && !visited[i]){
                //던전의 필요 체력보다 < 내 남은 체력이 커야 함
                //base case
                visited[i] = true;
                backtrack(n,k-dungeons[i][1],cnt+1,dungeons,visited);
                visited[i] = false;
            } 
        }
        //해당 안되면 함수 탈출이므로 continue 문 없어도 다음 for문으로 넘어감 (base case가 제약문으으로 적용)
    }
}

배우게 된 점

-base case를 따로 선언하지 않고 반복문 조건에 해당되지 않으면 넘어감.

-전역 변수로 답 선언해서 조건 걸고 갱신시키기.

-가장 큰 횟수를 구해야하므로 그 전보다 크면 갱신시키기

 

---

 

 

-이슈ⅰ

재귀 호출과 후위 연산자

//남은 체력 계산해서 재귀 호출
backtrack(cur_k-dungeons[i][1],visited,n,dungeons, cnt+1);

-이 부분에서 재귀로 함수를 호출할 때 cnt에 후위 연산자를 넣었더니 결과가 다르게 나옴

-이유1) cnt + 1은 현재 cnt 값에 1을 더한 값을 재귀 호출에 전달한다. 이 때 cnt 자체는 증가X 각 재귀 호출이 독립적으로 정확한 값을 전달받음.

⇒ 사실 cnt값 자체는 의미가 없다. 전달받은 값을 기준으로 연산을 수행하는 재귀 함수이므로 변수 값을 변환시키는 것이 중요하지X

이유2) cnt++는 후위 증가 연산자이므로 재귀 호출에 증가 전의 값을 전달함. 호출 후에 cnt를 증가시킴

 

-이슈ⅱ

더 많은 던전을 탐험한다=주어진 체력(k)으로 가능한 한 많은 던전을 방문하는 것

각 던전에는 필요한 최소 체력과 소모되는 체력이 있기 때문에, 어떤 순서로 던전을 탐험하는지에 따라 방문할 수 있는 던전의 수가 달라진다. 가능한 모든 경로를 탐색하여 최대한 많은 던전을 방문할 수 있는 최적 경로 찾기

⇒ 최적의 경로를 찾기 위해 모든 경로를 탐색

-이슈ⅲ

: 각 재귀 호출마다 answer 값을 유지하기 위해. 기본 자료형은 값만 복사되어 전달되기 때문에 갱신된 값이 호출 스택을 타고 올라가지 않음