[BOJ][🟡4][백준#12869] 뮤탈리스크

문제 출처

BAEKJOON Online Judge #12869

문제

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다. 각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다. 뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다.

첫 번째로 공격받는 SCV는 체력 9를 잃는다. 두 번째로 공격받는 SCV는 체력 3을 잃는다. 세 번째로 공격받는 SCV는 체력 1을 잃는다.

SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다. 남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 SCV의 수 N (1 ≤ N ≤ 3)이 주어진다. 둘째 줄에는 SCV N개의 체력이 주어진다. 체력은 60보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 SCV를 파괴하기 위한 공격 횟수의 최솟값을 출력한다.

예제

예제 1

입력

3
12 10 4

출력

2

예제 2

입력

3
54 18 6

출력

6

예제 3

입력

1
60

출력

7

예제 4

입력

3
1 1 1

출력

1

예제 5

입력

2
60 40

출력

9

My Sol

from collections import deque

def main():
    N = int(input())
    scvs = list(map(int, input().split()))
    Q = deque([(scvs, N, 0)])
    watched = set()
    damages = [
        [],
        [[9]],
        [[9,3], [3,9]],
        [[9,3,1],[9,1,3],[3,9,1],[3,1,9],[1,9,3],[1,3,9]]
    ]

    while Q:
        cur_scvs, scvs_cnt, attack_cnt = Q.popleft()
        if str(cur_scvs) in watched: continue
        watched.add(str(cur_scvs))

        for damage in damages[scvs_cnt]:
            attacked_scvs = []
            kill_cnt = 0
            for n in range(scvs_cnt):
                attacked_scv = cur_scvs[n] - damage[n]
                if attacked_scv <= 0:
                    kill_cnt += 1
                else:
                    attacked_scvs.append(attacked_scv)
            if kill_cnt == scvs_cnt: return attack_cnt+1
            Q.append((attacked_scvs, scvs_cnt-kill_cnt, attack_cnt+1))

print(main())

굉장히 쉽게 BFS로 풀 수 있는 문제였다.

1. 처음에 SCV의 개수와 체력 정보를 입력으로 받는다.
2. deque Q에 (SCV의 체력 정보 리스트, SCV 개수, 공격횟수)를 넣는다.
3. 같은 체력에 대한 공격을 진행했을 경우 같은 공격을 반복하지 않도록 사실상 방문 여부를 따지는 watched set을 둔다.
4. 각 SCV들의 수에 따라 공격의 패턴의 모든 경우의 수를 저장하는 damages 2차원 배열을 둔다.
5. deque Q에서 SCV 및 공격 정보를 하나씩 빼면서 조회하는데, SCV의 체력 정보를 문자열 처리한 것이 watched에 존재한다면 continue한다. 이때 문자열 처리한 이유는 list는 set에서 hash화할 수 없는 자료구조이기 때문이다. 때문에 그 자체로 string 처리하여 저장하고 조회했다. watched에 존재하지 않는다면, 첫 체력 구조인 것이기 때문에 watched에 현재 체력을 추가하고 공격을 시작한다.
6. SCV의 수에 따른 공격의 모든 경우의 수를 for문으로 반복처리한다. 현재 SCV 체력 리스트의 각 체력들에 대해 공격을 진행하고 체력이 0 이하가 된 SCV들의 수를 센다. 공격을 마치고 이 숫자가 공격 전 SCV의 수와 같다면 모든 SCV가 파괴된 것이므로 attack_cnt에 1을 더해 반환한다. 그렇지 않다면 아직 SCV가 남아있는 것이고, 이때의 SCV 체력은 attacked_scvs에 저장되어있으므로 이를 Q에 넣어 다음 공격에 사용한다. 이때 SCV의 체력들의 watched 처리를 제대로 하기 위해 모든 체력들은 오름차순 정렬한다. 만약 정렬하지 않으면 같은 체력 구성이더라도 순서가 달라 watched를 통과하게 되기 때문이다. 실제로 sort 과정을 통해 연산속도가 10% 향상되었음을 확인했다.
7. main 함수의 반환값을 출력한다.

처음에는 아래의 itertools의 순열 라이브러리를 사용해 damages 배열을 만들었다.

from itertools import permutations
def make_damages():
  damages = [9, 3, 1]
  D = [[] for _ in range(4)]
  for n in range(1, 4):
      D[n] = [lst for lst in permutations(damages[:n], n)]
  return D

damages = make_damages()

그런데 숫자가 그다지 많지 않기 때문에 그냥 하드코딩으로 변경했고, 시간상 차이는 많이 없었으나 코드 길이를 100B 가량 줄일 수 있었다.

결과

맞았습니다!!