문제:

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다.

각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다.

뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다.

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

SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다.

남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력:

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

출력:

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

풀이방법:

 SCV는 최대 3개까지만 있을 수 있기 때문에 이보다 더 적은 SCV가 들어온다면 0 배열을 이어 붙여서 길이가 3인 배열로 만들어 주도록 한다. SCV는 최대 체력이 60이고, 몇번째로 공격받느냐에 따라 체력이 달라지기 때문에 60의 길이를 가지는 3차원 visited 배열을 만든다.

 이후로는 BFS를 사용하여 나올 수 있는 경우의 수를 기반으로 체력을 감소시키며 모두 0이 되는 순간이 정답이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from itertools import permutations
from collections import deque
def bfs():
    q = deque([[scv, 0]])
    
    while q:
        state, count = q.popleft()
        if len(list(filter(lambda x: x>0, state)))==0:            
            break
        for attack in attacks:
            next_state = [0]*3
            for i in range(3):
                next_state[i] = max(0, state[i]-attack[i])
            if not visited[next_state[0]][next_state[1]][next_state[2]]:
                visited[next_state[0]][next_state[1]][next_state[2]] = 1
                q.append([next_state, count+1])
    return count
        
= int(input())
scv = list(map(int,input().split()))+[0]*(3-N)
visited = [[[0 for _ in range(61)]for _ in range(61)]for _ in range(61)]
attacks = list(permutations([9,3,1],3))
print(bfs())
cs

문제링크:

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

 

12869번: 뮤탈리스크

1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다.

www.acmicpc.net

 

'Algorithm > Python' 카테고리의 다른 글

[BOJ]12851. 숨바꼭질 2  (0) 2022.08.09
[BOJ]1189. 컴백홈  (0) 2022.08.04
[BOJ]2852. NBA 농구  (0) 2022.07.28
[BOJ]3474. 교수가 된 현우  (0) 2022.07.26
[BOJ]10709. 기상캐스터  (0) 2022.07.21

+ Recent posts