[프로그래머스] 피로도

이강혁·2023년 9월 5일

목록 보기

2/82

문제설명

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

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

제한사항

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

입출력 예

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

코드

//DFS

function solution(k, dungeons) {
var answer = [0, 0]; //answer 내부의 값 변경위해서 배열로 전달, 0번은 테스트용, 1번은 정답용(Max)만 저장

DFS(k, dungeons, answer);

return answer[1];
}

function DFS(k, dungeons, answer){//던전 돌기 전 체력, 던전들, count;
for(let i of dungeons){
    if(k < i[0]){//최소 체력보다 작을 때는 continue해서 다른 던전 선택
        continue;
    }else{
        k-=i[1];
        answer[0]++;
        answer[1] = answer[0]>answer[1]?answer[0]:answer[1]; //answer[1]은 최대 던전 수 저장하는 곳, answer[0]으로 테스트된 수가 더 크면 큰 거 줌.
        
        DFS(k, dungeons.filter((x, idx, arr) => idx != arr.indexOf(i)), answer)
        answer[0]--;
        k+=i[1];
    }
    
}
}

깊이 탐색을 이용해서 풀었음. DFS함수에 던전 돌기 전 체력, 전전, 던전 개수를 비교할 변수를 주고 현재 체력이 최소 체력보다 적을 때는 다음 던전 선택, 체력이 충분하면 해당 던전을 시작으로 나머지 던전을 DFS함수를 불러서 돌기 시작함.
filter를 사용해서 돌기 시작한 던전을 제외한 배열을 다시 만들었음.

다른 풀이

function solution(k, d) {
const N = d.length
const visited = new Array(N).fill(0)
let ans = 0

function dfs(k, cnt){
    ans = Math.max(cnt, ans)

    for (let j = 0; j < N; j++){
        if (k >= d[j][0] && !visited[j]){
            visited[j] = 1
            dfs(k - d[j][1], cnt + 1)
            visited[j] = 0
        }
    }
}

dfs(k, 0)
return ans;
}

내 풀이에서 filter를 사용해서 방문한 던전 제외시켰던 것과는 다르게 visited 배열을 만들어서 방문여부 판단함. 배열에 대한 메소드가 없는 다른 언어로 풀 때랑 비슷한 방식.

let solution = (k, d) => Math.max(...d.map(([m, v], i) => k < m ? 0 : solution(k - v, [...d.slice(0, i), ...d.slice(i + 1)]) + 1), 0)

k가 m보다 클 때 새로운 solution 함수 호출하는데 slice를 통해서 해당 index를 제외한 배열을 던전 매개변수에 넣어줬다. 코드 실행 결과는 0부터 시작해서 solution 함수가 호출될 때마다 1씩 더해졌고, map을 통해서 더한 결과가 d의 각 칸에 저장됨. 마지막으로 d를 스프레드해서 max를 구했다.

이강혁

사용자불량

이전 포스트

[프로그래머스] 최소직사각형

다음 포스트

[프로그래머스] 피로도