[BOJ/Gold 5] 백준 25330 SHOW ME THE DUNGEON(C++)

문제 링크

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

25330번: SHOW ME THE DUNGEON

 

문제

올 여름 출시된 RPG 게임 "SHOW ME THE DUNGEON"은 주인공 시루가 몬스터에게 침략당한 마을을 구하는 내용의 게임이다. 배경이 되는 나라는 0, 1, 2, ⋯, N번의 번호가 붙어있는 N + 1개의 마을로 이루어져 있다. 0번 마을과 1, 2, ⋯, N번 마을을 오갈 수 있는 도로가 존재하고 이 밖의 도로는 존재하지 않는다. 즉, N개의 도로가 존재한다.

게임이 시작하면 시루는 0번 마을에 위치하게 되며, 0번 마을을 제외한 1, 2, ⋯, N번 마을에는 몬스터가 각각 한 마리씩 있다. 시루는 마을을 방문할 때 도로를 통해 이동하며, 어떤 마을에서 다른 마을로 이동하기 위해서는 0번 마을을 거쳐야만 한다. 시루는 몇 개의 마을을 선택해 적당한 순서로 방문해 몬스터와 싸울 것이다.

 i번째 마을에 있는 몬스터의 공격력은 Ai이고 해당 마을에 Pi명의 주민이 있다. 시루는 어떤 마을을 방문하면 몬스터와 싸운 다음 마을에 있는 주민을 해방시킨다. 시루의 초기 체력은 K이고, 마을 i를 방문하기 전에 마을 t1, t2, ⋯, tk를 방문했다면, 마을 i에서 몬스터와 싸울 때 At1 + At2 + ⋯ + Atk + Ai만큼의 체력을 소모한다. 시루의 체력이 0보다 작아지는 경우, 주민을 해방시키지 못하고 게임이 종료된다.

모든 마을의 주민을 해방시키는 것은 불가능할 수 있기 때문에, 시루는 체력을 최대 K만큼만 소모하면서 최대한 많은 주민을 해방시키려고 한다. 시루가 해방시킬 수 있는 주민들의 최대 수를 구해보자.

입력

첫째 줄에 몬스터의 수 N과 시루의 초기 체력 K가 공백으로 구분되어 주어진다.

둘째 줄에 각 마을에 있는 몬스터의 공격력 A1, A2, ⋯, AN이 공백으로 구분되어 주어진다.

셋째 줄에 각 마을에 있는 주민의 수 P1, P2, ⋯, PN이 공백으로 구분되어 주어진다.

입력으로 주어지는 모든 값은 정수이다.

출력

시루가 해방시킬 수 있는 주민들의 최대 수를 출력한다. 만약 주민을 해방시킬 수 없다면 0을 출력한다.

제한

•  1 ≤ N ≤ 20
•  1 ≤ K ≤ 100,000
•  1 ≤ Ai ≤ 100,000
•  1 ≤ Pi ≤ 100,000

예제 입력 1

5 5
5 3 1 2 4
10 10 10 10 10

예제 출력 1

20

4번 마을과 3번 마을을 차례로 방문하면 2 + (2 + 1) = 5의 체력을 소모해서 20명의 주민을 해방시킬 수 있다.

예제 입력 2

5 100
1 1 1 1 1
10 10 10 10 10

예제 출력 2

50

예제 입력 3

5 1
2 2 2 2 2
2 2 2 2 2

예제 출력 3

0

알고리즘 분류

• 백트래킹

풀이

아직 방문하지 않은 마을을 방문하면서 해당 마을에 있는 몬스터의 공격력 + 지금까지 입은 피해량만큼 시루의 체력을 깎고 구한 주민의 수를 마을에 있는 주민들의 수만큼 증가시킨다.

이것을 재귀로써 풀이하는데, 만약 현재 시루의 체력이 0 이하이거나, 시루가 앞으로 구할 수 있는 주민의 수가 현재까지 따진 경우의 수 중 구할 수 있는 주민의 수의 최댓값보다 작다면 재귀를 종료한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 21
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, K;
int A[MAX], P[MAX];
bool Visited[MAX];
int Answer;

void input() {
    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
    for (int i = 1; i <= N; i++) {
        cin >> P[i];
    }
}

void DFS(int Health, int People, int Sum) {
    Answer = max(Answer, People);
    if (Health <= 0) {
        return;
    }
    int Remain = 0;
    for (int i = 1; i <= N; i++) {
        if (!Visited[i] && (Sum + A[i] <= Health)) {
            Remain += P[i];
        }
    }
    if (People + Remain <= Answer) {
        return;
    }
    for (int i = 1; i <= N; i++) {
        if (!Visited[i] && (Sum + A[i] <= Health)) {
            Visited[i] = true;
            DFS(Health - (Sum + A[i]), People + P[i], Sum + A[i]);
            Visited[i] = false;
        }
    }
}

void settings() {
    DFS(K, 0, 0);
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}