[백준 - 25330] SHOW ME THE DUNGEON - Java

문제 설명

 

25330번: SHOW ME THE DUNGEON

 

접근 방법

해당 문제에서는 캐릭터(시루)의 체력과 마을별 몬스터의 공격력과 주민의 수가 주어졌을 때 시루가 해방시킬 수 있는 주민들의 최대 수를 요구하고 있습니다.

 

접근 방법 1 : 순열 - 시간 초과

처음 이 문제에 접근했었던 방식은 시루가 각각의 던전들을 순서를 고려하면서 방문하는 모든 경우의 수(순열)를 구함으로써 해방시킬 수 있는 주민들의 최대 수를 구하는 것이었습니다. (다만, 시루의 체력이 소진되지 않는 선에서 탐색 진행) 다음은 이에 대한 로직입니다.

 

    private static void hunt(boolean[] visited, int hp, int damaged, int savedPeopleCount) {
        result = Math.max(result, savedPeopleCount);

        for (int i = 1; i <= n; i++) {
            if (!visited[i] && hp >= damaged + monsters[i]) {
                visited[i] = true;
                hp -= (damaged + monsters[i]);
                savedPeopleCount += people[i];
                damaged += monsters[i];

                hunt(visited, hp, damaged, savedPeopleCount);

                damaged -= monsters[i];
                hp += (damaged + monsters[i]);
                savedPeopleCount -= people[i];
                visited[i] = false;
            }
        }
    }

 

하지만 현재 문제에서 주어진 던전의 개수 N 은 최대 20으로서 이러한 방식으로 접근하면 극단적인 상황에서 20!(=2,432,902,008,176,640,000) 가지의 경우의 수를 모두 탐색해야 할 수도 있습니다. (시간 초과)

 

접근 방법 2 : 정렬과 부분 집합

시루의 체력은 k로 한정되어있으며 체력 소모도 어느 던전을 먼저 방문하냐에 따라 달라지기 때문에 순열로 접근하는 방식은 매우 직관적이긴 하나, 이 접근 방법의 문제점은 '불필요하게 너무 많은 탐색'이 발생한다는 것입니다.

 

좀 더 효율적인 탐색에 있어 중요한 포인트는 시루가 k 라는 한정된 체력 안에서 최대한 많은 주민을 해방시켜야 한다는 것입니다. 이때 체력을 가장 효율적으로 소모할 수 있는 방법은 몬스터의 공격력이 적은 순으로 방문하는 것입니다. 따라서 몬스터의 공격력을 오름차순으로 정렬한 뒤에 각각의 던전을 순차적으로 방문해보는 방식을 떠올릴 수 있습니다.

 

하지만, 몬스터의 공격력이 적다고 해서(체력을 효율적으로 소모한다고 해서) 많은 주민을 해방시키리라는 보장은 없습니다. 이러한 점을 보완코자 부분 집합 방식을 떠올릴 수 있습니다. 몬스터의 공격력이 적은 순으로 방문하되, 많은 수의 주민을 해방시키고자 탐색 시 선택과 비선택을 나누는 것입니다. 이때, 시루의 체력이 중간에 모두 소진될 경우 더이상의 탐색은 의미가 없으므로 가지치기 효과도 있어 좀 더 효율적인 탐색이 가능해집니다. 혹여라도 극단적인 상황에서 모든 던전을 탐색하더라도 N이 최대 20이기에 2^20(=1,048,576)으로 충분히 제한 시간 내에 탐색해볼만한 경우의 수에 해당됩니다.

 

전체 소스 코드

import java.util.Arrays;
import java.util.Comparator;

class Main {

    static int result = 0;
    static int[][] info;

    public static void main(String[] args) throws Exception {
        int n = read(), hp = read();
        info = new int[n][2];

        for (int i = 0; i < n; i++) {
            info[i][0] = read();
        }

        for (int i = 0; i < n; i++) {
            info[i][1] = read();
        }

        Arrays.sort(info, Comparator.comparingInt(o -> o[0]));

        hunt(0, n, hp, 0, 0);

        System.out.println(result);
    }

    private static void hunt(int depth, int n, int hp, int damaged, int savedPeopleCount) {
        if (depth == n) {
            return;
        }

        if (hp < damaged + info[depth][0]) {
            return;
        }

        hp -= (damaged + info[depth][0]);
        savedPeopleCount += info[depth][1];
        damaged += info[depth][0];

        result = Math.max(result, savedPeopleCount);

        hunt(depth + 1, n, hp, damaged, savedPeopleCount);

        damaged -= info[depth][0];
        hp += (damaged + info[depth][0]);
        savedPeopleCount -= info[depth][1];

        hunt(depth + 1, n, hp, damaged, savedPeopleCount);
    }

    private static int read() throws Exception {
        int c, n = System.in.read() - 48;
        while ((c = System.in.read()) > 32) n = 10 * n + c - 48;
        return n;
    }
}

 

참고자료

• https://www.acmicpc.net/problem/25330