99클럽 - 거리 두기 게임

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

아이디어

• 끝과 끝 사이의 거리가 D보다 작다면 이길 수 없다.
• 각 칸에서 가능한 최대 책시 거리가 D 미만이라면 해당 칸을 차단해야 한다.
• 출력은 차단한 칸들의 집합이다.

풀이

N, M = map(int, input().split())
D = int(input())

max_distance_from_edge = (N-1) + (M-1)
if max_distance_from_edge < D:
    min_blocks = 0
else:
    required_blocks = [[0] * M for _ in range(N)]
    
    for i in range(N):
        for j in range(M):
            furthest_distance = max(
                i + j,
                (N-1-i) + j,
                i + (M-1-j),
                (N-1-i) + (M-1-j)
            )
            
            if furthest_distance < D:
                required_blocks[i][j] = 1
    
    min_blocks = sum(sum(row) for row in required_blocks)

print(min_blocks)