문제 소개
n개의 행(row)과 m개의 열(column)로 이루어진 격자(grid)가 있다고 가정해 봅시다. 아말(Amal)과 비말(Bimal)은 이 격자 위에서 다음과 같은 규칙으로 게임을 진행합니다.
게임 규칙
아말은 맨 윗줄의 아무 곳에나 흰색 연꽃(lotus) 타일을 놓고, 비말은 맨 아랫줄의 아무 곳에나 애벌레(caterpillar) 타일을 놓습니다. 아말이 선공이며, 두 플레이어는 번갈아 가며 자신의 타일을 움직입니다.
- 아말(연꽃): 현재 칸을 기준으로 격자 내부에 있는 인접한 8개 칸 중 어느 곳으로든 이동할 수 있습니다.
- 비말(애벌레): 격자 안에서 왼쪽 또는 오른쪽으로만 이동할 수 있으며, 제자리에 그대로 머무는 것도 허용됩니다.
아말의 목표는 최소한의 이동으로 비말을 잡는 것이고, 비말의 목표는 애벌레 타일로 최대한 오래 생존하는 것입니다. 만약 두 사람이 각자 타일을 놓을 열을 무작위로 선택한다면, 아말이 이 게임에서 승리하기 위해 필요한 기대 이동 횟수(expected number of moves)를 구해야 합니다.
예시
예를 들어 입력이 n = 5, m = 7이라면 출력은 4.571428571428571이 됩니다.
풀이 접근 방법
이 문제는 다음 절차를 따라 해결할 수 있습니다.
- r := 0으로 초기화합니다.
- l을 0부터 m − 1까지 순회하며 다음을 반복합니다.
- temp := n − 1.0
- l ≥ n인 경우: temp := temp + (l − n + 1) × ((l − 1) / m)
- l < m − n인 경우: temp := temp + (m − n − l) × ((m − l − 2) / m)
- r := r + temp / m
- 모든 반복이 끝나면 r을 반환합니다.
핵심 아이디어는 각 시작 열 위치별로 필요한 이동 횟수를 계산한 뒤, 이를 모든 가능한 위치에 대해 평균 내는 것입니다. 세로 방향으로는 최소 n − 1번의 이동이 필수적이며, 격자의 가장자리에 가까운 위치일수록 애벌레가 회피할 수 있는 공간이 줄어들기 때문에 조건식을 통해 이를 보정해 줍니다.
구현 코드
아래 파이썬 구현 예제를 통해 더 잘 이해해 봅시다.
def solve(n, m):
r = 0
for l in range(m):
temp = n - 1.0
if l >= n:
temp += (l - n + 1) * ((l - 1) / m)
if l < m - n:
temp += (m - n - l) * ((m - l - 2) / m)
r += temp / m
return r
n = 5
m = 7
print(solve(n, m))입력
5, 7
출력
4.571428571428571