카드팩을 구하여 카드뭉치를 만들고 정해진 규칙에 따라 상대와 겨루는 게임을 'Collectible Card Game(CCG)'이라 부른다. 요즘 현정이와 준표가 즐기는 '돌게임'도 CCG 중 하나다.
돌게임에는 '하수인' 카드와 '주문' 카드가 있다. '하수인'이란 공격력과 생명력을 가진 개별적인 개체로 다른 게임의 몬스터와 비슷하다. '주문'이란 '전장'에 다양한 효과를 발휘하는 카드로 다른 게임의 마법과 비슷하다. '전장'이란 두 플레이어가 하수인을 배치하는 공간으로 다른 게임의 필드와 비슷하다.
돌게임의 주문카드 중에 '모독'이라는 카드가 있다. 이 카드는 전장에 있는 모든 하수인에게 피해를 1씩 주고, 이로 인해 죽은 하수인이 있다면 이 효과를 반복한다. 하수인은 피해를 받을 때마다 그만큼 생명력이 감소하며, 생명력이 0 이하가 되는 순간 죽는다. 주의할 것은 한 번에 여러 하수인이 죽었더라도 이로 인한 모독의 추가 반복 횟수는 1번이다. 예를 들어 전장에 생명력이 1, 1, 2, 3, 5인 다섯 하수인이 존재하는 상태에서 모독을 사용하면 생명력이 1인 하수인이 먼저 죽고, 이후 추가 발동으로 생명력이 2였던 하수인이 죽고, 이후 추가 발동으로 생명력이 3이었던 하수인이 죽는다. 이때 다시 한 번 모독이 발동하지만 생명력이 5였던 하수인은 생명력이 1이 된 상태에서 살아남고, 이번 모독으로 죽은 하수인이 없으므로 더 이상 반복하지 않는다.
각 플레이어는 자신의 턴에 하수인을 사용하여 공격할 수 있으며 돌게임에서 하수인 X가 하수인 Y를 공격하면 아래의 일이 동시에 발생한다.
하수인 X의 공격력만큼 하수인 Y가 피해를 받는다. 하수인 Y의 공격력만큼 하수인 X가 피해를 받는다.
'모독각'이란 자신의 하수인과 모독을 통해 상대방의 모든 하수인을 죽이는 상황을 뜻한다. 준표는 유독 모독각을 계산하지 못하는 현정이를 위해 모독 알리미를 선물하려 한다. 하지만 전자과인 준표는 학업만으로도 바빠 알리미 제작을 여러분에게 부탁했다.
현정이의 전장에는 이번 턴 한 번씩만 공격 가능한 하수인이 N개 있다. 현정이와 상대 전장의 하수인 정보가 주어졌을 때 현정이의 하수인들과 모독 한 장으로 상대 전장에 있는 하수인을 모두 처치할 수 있는지 판단하고, 있다면 어떤 순서로 이를 이룰 수 있는지 알려주는 프로그램을 작성해보자.
첫 줄에 현정의 전장에 있는 하수인 수 N과 상대 전장의 하수인 수 M이 주어진다. (0 ≤ N, M ≤ 7)
이후 N줄에 걸쳐 차례로 현정이 전장의 1 ~ N번 하수인의 공격력과 생명력이 주어진다. 이후 M줄에 걸쳐 차례로 상대 전장의 1 ~ M번 하수인의 공격력과 생명력이 주어진다. 모든 공격력과 생명력은 양의 정수이며 12를 넘지 않는다
출력
가능하다면 첫 줄에 로그의 개수 L(0 ≤ L ≤ N+1)을 출력한다.
이후 L개의 줄에 걸쳐 모독각을 만드는 로그를 한 줄씩 출력한다. 모든 로그는 순차적으로 처리되며 각 로그의 순서에 가능한 상황이어야 한다. 로그의 종류는 아래와 같다.
"attack n m": 현정이 전장의 n번 하수인이 상대 전장의 m번 하수인을 공격한다. 이때 두 하수인은 모두 죽지 않은 상태여야 한다. 현정이 전장의 어떤 하수인 n의 공격 로그는 최대 한 번 등장할 수 있다. 자신보다 앞 번호의 하수인이 죽었더라도 하수인의 번호는 변하지 않는다.
"use modok": 모독을 사용한다. 이 로그도 최대 한 번 등장할 수 있다.
가능한 로그의 종류가 여럿이라면 그 중 아무것이나 출력한다. 불가능하면 한 줄에 -1을 출력한다.
입력 예시
출력 예시
풀이
구현 문제. 모든 경우의 수를 테스트할 만큼 경우의 수가 작으므로 브루트포스를 시도해 볼 법하다.
경우의 수는
아군 하수인이 공격하는 순서의 경우의 수 : N! < 7!
각 아군 하수인이 상대 하수인을 공격하는 경우의 수 : 최대 8^7 (공격하지 않는 경우를 포함)
모독을 사용하는 경우
가 있겠다. 실제로는 상대 하수인의 체력이 0인 경우가 제외되므로 경우의 수는 훨씬 작아진다. 모독을 사용하는 경우에 대한 구현만 주의하자. 모독을 사용할 경우
1부터 최대 연속 체력 배열의 길이가 데미지가 된다 (가령 [1, 3]일 경우 데미지는 3이다.)
모든 하수인에게 이 데미지를 가한다.
가 성립한다.
풀이 코드
from itertools import permutations
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
minions =[]
total = { key : 0 for key in range(13) }
log = []
enemy_left = M
for i in range(N+M) :
a, h = map(int, input().split())
minions.append([a, h])
total[h] += 1
def change_val(i, orig, changed) :
minions[i][1] = changed
total[orig] -= 1
total[changed] += 1
def modok(n, md) :
global enemy_left
if md :
return False
dmg = 1
for i in range(1, 13) :
if not total[i] :
break
dmg += 1
diff_list = []
for i in range(N+M) :
if not minions[i][1] :
continue
diff = max(0, minions[i][1] - dmg)
diff_list.append((i, minions[i][1], diff))
change_val(i, minions[i][1], diff)
if i >= N and not diff :
enemy_left -= 1
log.append((0, 0))
if dfs(n, 1) :
return True
log.pop()
for i, orig, diff in diff_list :
change_val(i, diff, orig)
if i >= N and not diff :
enemy_left += 1
return False
def dfs(n, md) :
global enemy_left
if not enemy_left :
return True
if n == N :
return modok(n, md)
if dfs(n+1, md) :
return True
for i in range(M) :
if not minions[i+N][1] :
continue
oa, oh = minions[perm[n]]
ea, eh = minions[N+i]
o_diff = max(oh-ea, 0)
e_diff = max(eh-oa, 0)
log.append((perm[n]+1, i+1))
change_val(perm[n], oh, o_diff)
change_val(N+i, eh, e_diff)
if not e_diff :
enemy_left -= 1
if dfs(n+1, md) :
return True
if not e_diff :
enemy_left += 1
log.pop()
change_val(perm[n], o_diff, oh)
change_val(N+i, e_diff, eh)
return modok(n+1, md)
for perm in permutations(range(N)) :
result = dfs(0, 0)
if result :
break
if not result :
print("-1")
else :
print(len(log))
for i, j in log :
if i :
print("attack", i, j)
else :
print("use modok")
