[BaekJoon] 25330 SHOW ME THE DUNGEON (Java)

1.  문제 링크

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

2.  문제

요약

• "SHOW ME THE DUNGEON"은 주인공 시루가 몬스터에게 침략당한 마을을 구하는 내용의 게임입니다.
• 배경이 되는 나라는 0, 1, 2, ... N번의 번호가 붙어있는 N + 1개의 마을로 이루어져 있습니다.
• 0번 마을과 1, 2, ..., N번 마을을 오갈 수 있는 도로 N개가 존재하고 이 밖의 도로는 존재하지 않습니다.
• 게임이 시작되면 시루는 0번 마을에 위치하고, 1, 2, ..., N번 마을에는 몬스터가 각각 한 마리씩 있습니다.
• 시루는 마을을 방문할 때 도로를 통해 이동하며, 어떤 마을에서 다른 마을로 이동하기 위해서는 0번 마을을 거쳐야만 합니다.
• i번째 마을에 있는 몬스터의 공격력은 $A_i$이고 해당 마을에 $P_i$명의 주민이 있습니다.
• 시루는 어떤 마을을 방문하면 몬스터와 싸운 다음 마을에 있는 주민을 해방시킵니다.
• 시루의 초기 체력은 K이고, 마을 i를 방문하기 전에 마을 $t_1, t_2, ..., t_k$를 방문했다면, 마을 i에서 몬스터와 싸울 때 $A_{t_1} + A_{t_2} + ... + A_{t_k} + A_i$만큼의 체력을 소모합니다.
• 시루의 체력이 0보다 작아지는 경우, 주민을 해방시키지 못하고 게임이 종료됩니다.
• 체력을 최대 K만큼 소모하면서 시루가 해방시킬 수 있는 주민들의 최대 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 20보다 작거나 같은 몬스터의 수 N과 1보다 크거나 같고 100,000보다 작거나 같은 시루의 초기 체력 K가 주어지고 두 번째 줄에 1보다 크거나 같고 100,000보다 작거나 같은 각 마을에 있는 몬스터의 공격력 $A_1, A_2, ..., A_N$이 주어지며 세 번째 줄에 1보다 크거나 같고 100,000보다 작거나 같은 각 마을에 있는 주민의 수 $P_1, P_2, ..., P_N$이 주어집니다.
  • 입력으로 주어지는 모든 값은 정수입니다.
• 출력: 첫 번째 줄에 시루가 해방시킬 수 있는 주민들의 최대 수를 출력합니다. 만약 주민을 해방시킬 수 없다면 0을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.StringTokenizer;

public class Main {
    static int N, K, answer;
    static int[] attackPowers, residents;
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        K = scanner.nextInt();
        attackPowers = new int[N + 1];
        residents = new int[N + 1];
        for(int idx = 1; idx <= N; idx++) attackPowers[idx] = scanner.nextInt();
        for(int idx = 1; idx <= N; idx++) residents[idx] = scanner.nextInt();
    }

    static void solution() {
        answer = 0;
        rec_func(0, 0, 0, 0, new boolean[N + 1]);
        System.out.println(answer);
    }

    static void rec_func(int sum, int prev, int resident, int count, boolean[] visited) {
        if(sum <= K) answer = Math.max(answer, resident);
        if(sum > K) return;
        for(int idx = 1; idx <= N; idx++) {
            if(!visited[idx]) {
                visited[idx] = true;
                int exhaustion = prev + attackPowers[idx];
                rec_func(sum + exhaustion, exhaustion, resident + residents[idx], count + 1, visited);
                visited[idx] = false;
            }
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return str;
        }
    }
}

4.  접근

• 각 마을을 방문할 수 있는 경우의 수들을 모두 방문해보면서 그 중 해방시킬 수 있는 가장 많은 주민의 수를 찾습니다.
  • 각 마을을 방문했는지를 나타내는 배열 visited를 생성합니다.
  • 현재 마을 전까지 소모한 체력, 현재 마을에서 소모한 체력, 현재까지 해방시킨 주민의 수, 현재까지 방문한 마을의 수를 계산하여 해방시킬 수 있는 가장 많은 주민의 수를 찾습니다.
    • 만약 현재 마을 전까지 소모한 체력이 K보다 크다면 더이상 다른 마을을 방문할 수 없으므로 다른 경우의 수를 확인합니다.
    • 만약 현재 마을 전까지 소모한 체력이 K보다 작거나 같다면 현재까지 해방시킨 주민의 수와 그 전까지의 해방시킨 최대 주민의 수를 비교하여 그 중 큰 값으로 갱신합니다.
    • 아직 방문하지 않은 마을들을 방문하면서 현재 마을에서 소모한 체력 및 현재 마을까지 소모한 체력, 현재 마을까지 해방시킨 주민의 수를 계산하여 해방시킬 수 있는 최대 주민의 수를 구합니다.