17135: 캐슬 디펜스

풀이 시간

• 1h 35m
• 이 문제에서도 마찬가지로 "궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다." 와 같은 조건이 있었다. 이러한 조건은, 가능한 경우를 모두 구해주고 정렬을 통해서 처리해주는 방식으로 해야 안정적으로 조건을 만족시킬 수 있는 것 같다.

구현 방식

• combinations를 통해 3명의 궁수를 놓는 모든 경우를 탐색해줘야 한다

• 궁수의 공격
  -> 문제의 조건: "궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다"
  -> 최상의 for문을 궁수로 잡고 일단 board를 순회하면서 board[i][j] == 1이고 궁수와의 거리가 D이하인 모든 경우를 tmp 리스트에 넣어준다
  -> 궁수 별로 tmp 리스트를 오름차순으로 정렬하고 가장 조건에 맞는 적을 will_death 리스트에 넣어준다
  -> will_death 리스트를 완성한 후에 적을 죽이고 local_max_dead를 갱신해준다

• 적 이동
  -> board를 역순으로 가장 윗줄 전까지 순회하면서 현재 row를 이전 row로 할당해준다
  -> 그 후에 가장 윗줄의 row를 모두 0으로 할당해준다

코드

import sys
from itertools import combinations
import copy


N, M, D = map(int, sys.stdin.readline()[:-1].split())
origin_board = []
for n in range(N):
    origin_board.append(list(map(int, sys.stdin.readline()[:-1].split())))

archers = list(combinations([idx for idx in range(M)], 3))

max_dead = 0 #구하고자 하는 값
for archer in archers:

    board = copy.deepcopy(origin_board)
    local_max_dead = 0

    while True:
        ##### 궁수의 공격
        will_death = []
        for arc in archer:
            tmp = [] #하나의 archer당 가능한 적
            for i in range(N-1, -1, -1): #열 거꾸로 순회
                for j in range(M):
                    if board[i][j] == 1 and abs(i - N) + abs(j - arc) <= D:
                        tmp.append((abs(i - N) + abs(j - arc), j, i))
            if tmp:
                tmp.sort()
                will_death.append(tmp[0]) #조건에 맞는 적을 넣어줌
        
        cnt = 0
        for wd in will_death: #적 죽이기
            d, j, i = wd
            if board[i][j] == 1:
                board[i][j] = 0
                cnt += 1
        local_max_dead += cnt

        ##### 적 이동
        for i in range(N-1, 0, -1):
            board[i] = board[i-1]
        board[0] = [0 for _ in range(M)]

        ##### 종료조건 확인
        t = 0
        for i in range(N):
            t += sum(board[i])
        if t == 0:
            break

    max_dead = max(max_dead, local_max_dead)

print(max_dead)

결과

• indexError 발생 이유: 궁수의 공격을 구현하는 과정에서, 열 순회의 범위를 for i in range(N-1, N-1-D, -1)로 잡았었는데 이때 D가 N보다 크게 주어질 경우가 반례였던 것 같다 -> for i in range(N-1, -1, -1)로 그냥 다 순회하도록 변경