[백준] 25330. SHOW ME THE DUNGEON - Python3

문제 설명

0번 마을을 제외한 N개의 마을에 각각 몬스터 한 마리와, 갇혀있는 주민들이 있다. 주인공 시루는 각 마을의 몬스터와 싸워 최대한 많은 수의 주민들을 구하려고 하는데, 각 마을을 방문할 때마다 소모되는 체력은 (이전까지 소모한 체력+이번 마을 몬스터 체력)이다. 몬스터 수 N, 시루의 초기 체력 K, 1~N번 마을에 있는 몬스터의 공격력 A1, A2, ..., AN, 각 마을에 있는 주민 수 P1, P2, ..., PN이 공백으로 구분되어 주어질 때, 시루가 해방시킬 수 있는 주민들의 최대 수를 구하는 문제

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

25330번: SHOW ME THE DUNGEON

• 알고리즘 분류 - 브루트포스, 비트마스킹
• 난이도 - 골드 5

---

주의사항

체력이 은근 골칫거리다. 코드 짜다보면 계속 헷갈릴 수 있어서 소모 체력이 누적되는 방식을 제대로 이해하고, 체력 로직을 충분히 고민해야 한다.

또, 재귀 사용 시 종료 조건이 너무너무 중요하다. 최대한 pruning 할 수 있는 조건을 고민해봐야 한다.

---

관련 개념

비트마스킹, 백트래킹

---

접근 방법

1. Permutations - 시간초과

각 마을을 방문하는 순서에 대한 모든 경우에 대해 해방 가능한 주민 수를 구하기 때문에 쉽게 최적의 해를 찾을 수 있겠지만, permutations에 대해 반복문을 수행하는 순간 pruning이 전혀 안 되기 때문에(아마?) O(N!)이 그대로 적용돼 시간 초과가 발생한다.

 

2. 비트마스킹

(다른 분 코드 참고)

각 마을의 방문여부를 0과 1로 나타내고, 각 경우에 구할 수 있는 마을주민 수를 저장할 수 있도록 비트마스킹을 활용했다.

가령, 첫번째 마을과 마지막 마을을 방문해 10명을 구했다면, 방문여부는 1 0 0 0 1이 될 것이고, 이는 십진수로 변환하면 17이다.

array[17] = 10 이 되도록 array 배열을 만든다는 것이다.

이 때, 비트마스킹은 순열이 아닌 조합을 표현할 수 있는 방법이다. 이 문제에선 방문 순서도 중요하므로 순열이 필요한데, 모든 순열을 구하면 효율이 좋지 않으므로 방문이 예정된 마을 중 체력이 가장 적게 드는 마을부터 방문하도록 한다. 따라서, 방문할 마을 번호에 대한 조합을 먼저 새로운 배열에 저장한 뒤, 체력이 적게 드는 마을부터 방문하도록 배열을 정렬한다.

 

3. 재귀(백트래킹) - 가장 효율적

(다른 분 코드 참고)

0번 마을을 통해 모든 마을에서 다른 마을로 이동할 수 있으므로, 각 마을에서 다른 마을을 dfs로 방문하는 코드를 짠다.

진짜로 다 방문해버리면 비효율적이므로 백트래킹을 이용하는데, 더 이상 탐색할 필요가 없어져 가지치기를 할 수 있는 경우는 다음 두 가지다.

1) 주민을 구한 뒤 체력이 0이 됐다. => 탐색 불가

2) (현재까지 구한 주민 수 + 현재까지의 체력으로 방문할 수 있는 마을들에 남아 있는 주민수)가 현재까지의 최대 해방 주민수보다 적다. => 남은 마을들을 다 방문해도 어차피 최댓값보다 적으므로 탐색할 가치가 없다.

이 두 가지 종료조건만 설정해주고, 재귀호출 시 소모된 체력만 인자로 잘 넘겨주면 끝난다.

---

답안 코드

1. Permutations

메모리: 30864 KB , 시간: 72 ms, 코드 길이: 140 B

import sys
from itertools import permutations
input = sys.stdin.readline

n,k = map(int, input().split())
A = list(map(int, input().split()))
P = list(map(int, input().split()))

answer = 0

for seq in permutations(list(range(n)),n):
    hp = k
    damage = 0
    saved = 0
    
    for i in seq:
        if hp == 0:
            break
        
        damage += A[i]
        hp -= damage
        
        if hp < 0:
            break
        
        saved += P[i]
        if saved > answer:
            answer = saved
                
print(answer)

 

2. 비트마스킹

메모리: 68176 KB , 시간: 7896 ms, 코드 길이: 610 B

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
A = list(map(int, input().split()))
P = list(map(int, input().split()))

arr = [0 for _ in range(1 << n)]

for i in range(1<<n):
    hp = 0
    visited = []
    
    bits = bin(i)[2:].zfill(n)
    for j in range(n):
        if bits[j] == '1':
            visited.append([j,A[j]])
            
    visited.sort(key = lambda x:x[1])
    
    for j in range(len(visited)):
        dungeon = visited[j][0]
        hp += A[dungeon] * (len(visited)-j)

        if hp > k:
            break

        arr[i] += P[dungeon]
        
print(max(arr))

 

3. 재귀 (백트래킹)

메모리: 31256 KB , 시간: 44 ms, 코드 길이: 658 B

def solution(hp, damage, saved):
    global answer

    answer = max(answer, saved)
    
    if not hp:
        return
    
    remain = sum([P[i] for i in range(n) if not visited[i] and damage+A[i] <= hp])
    
    if saved + remain <= answer:
        return
    
    for i in range(n):
        if not visited[i] and damage+A[i] <= hp:
            visited[i] = True
            solution(hp-damage-A[i], damage+A[i], saved+P[i])
            visited[i] = False
        
n,k = map(int, input().split())
A = list(map(int, input().split()))
P = list(map(int, input().split()))
visited = [False for _ in range(n)]
answer = 0
        
solution(k,0,0)
print(answer)

 

 

와 한 달을 애먹은 증오스러운 문제다.... 애초에 제출 수도 적은 문제고, 공개된 파이썬 답안도 없고, 구글링 해봐도 재채점 이전 해답들이라 지금은 시간초과가 나 아무 도움이 안 됐다. 비트마스킹으로 풀어주신 스터디장님 아니었음 내 실력으론 절대 해결 못했을 듯... 

+) 다음부턴 죽어도 안 풀리면 알고리즘 분류 먼저 펼쳐보자...

+) 그나저나 이거 풀려고 비트연산도 다시 공부했는데 재귀가 더 효율적이었다니...ㅋㅋ dfs, bfs, 백트래킹 연습 진짜 많이 해야겠다.