99클럽 코테 스터디 17일차 TIL - [백준/파이썬] - 30052 거리 두기 게임

[Silver III] 거리 두기 게임 - 30052

문제 링크

성능 요약

메모리: 112972 KB, 시간: 148 ms

분류

애드 혹

제출 일자

2024년 4월 26일 23:03:49

문제 설명

준성이와 효석이는 N×M$N \times M$ 크기의 격자판 위에서 게임을 하고 있다. 규칙은 다음과 같다.

• 준성이와 효석이는 각자 말을 한 개씩 가지고 시작한다.
• 효석이는 준성이가 말을 둘 수 없는 격자 칸 A$A$개를 정한다.
• 준성이는 말을 둘 수 있는 격자 칸 중 하나에 말을 두고, 효석이는 준성이가 말을 둔 격자 칸을 제외한 모든 격자 칸 중 하나에 말을 둔다.
• 두 말 사이의 택시 거리가 D$D$보다 작으면 준성이가, 같거나 크면 효석이가 승리한다.

준성이와 효석이가 최선을 다해 게임을 진행했을 때, 효석이가 승리할 수 있는 A$A$의 최솟값을 구하여라.

단, 효석이가 승리할 수 없는 경우는 입력으로 주어지지 않는다.

입력

첫 번째 줄에 격자판의 세로 길이인 정수 N$N$ , 가로 길이인 정수 M$M$이 공백으로 구분되어 주어진다. (3≤N,M≤400)$(3 \leq N, M \leq 400)$ 

두 번째 줄에 두 말 사이의 택시 거리인 정수 D$D$가 주어진다. (2≤D≤798)$(2 \leq D \leq 798)$ 

출력

효석이가 승리할 수 있는 A$A$의 최솟값을 출력한다.

 

풀이

n, m = map(int, input().split())
d = int(input())
ans = 0
arr = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(1, n+1) :
    for j in range(1, m+1) :
        if abs(1-i) + abs(1-j) < d :
            arr[i][j] = 1

        if abs(n-i) + abs(1-j) < d and arr[i][j] == 1 :
            arr[i][j] = 2

        if abs(1-i) + abs(m-j) < d and arr[i][j] == 2 :
            arr[i][j] = 3

        if abs(n-i) + abs(m-j) < d and arr[i][j] == 3 :
            ans += 1

print(ans)

이 문제를 해결하기 위해서는 격자판 위에서 특정 조건을 만족하는 칸의 수를 계산해야 한다. 문제에서 주어진 조건은 두 말 사이의 택시 거리가 D보다 작으면 준성이가, 같거나 크면 효석이가 이기는 것이다. 효석이가 승리하기 위해서는 준성이가 말을 둘 수 있는 격자 칸을 최소한으로 줄여야 한다. 이를 위해 효석이는 준성이가 말을 둘 수 없는 격자 칸 A개를 정해야 한다. 

효석이가 승리하기 위해 A의 최솟값을 구하는 문제이다. 먼저, 격자판의 각 칸에서 가장 가까운 모서리까지의 택시 거리를 계산해야 한다. 이 거리가 D보다 작은 칸들은 준성이가 말을 둘 수 없으므로, 효석이가 이길 수 있는 조건을 만족한다. 이런 칸들의 수를 최소화하기 위해, 격자판의 모서리에서 거리가 D-1 이내인 칸들을 찾아야 한다.

1. 격자판의 모든 칸을 순회하면서, 각 칸에서 네 모서리까지의 택시 거리를 계산한다.
2. 택시 거리가 D-1 이하인 칸의 수를 세어 A의 값을 구한다.

이 코드의 핵심 아이디어는 각 격자 칸이 네 모서리로부터 택시거리 D 이내에 위치하는지 여부를 확인하여, 효석이가 승리할 수 있는 조건을 만족하는 격자 칸의 수를 계산하는 것이다. 각 단계에서 격자 칸의 상태를 업데이트하며, 최종적으로 상태가 3으로 설정된 격자 칸의 수가 바로 효석이가 승리하기 위해 준성이가 말을 둘 수 없는 격자 칸 A의 최소 개수가 된다.