[BOJ] 15488 나이트가 체스판을 벗어나지 않을 확률

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

나이트가 K번 지멋대로 움직일 때 체스판을 벗어나지 않고 남이있을 확률을 구하는 문제이다.

일반적인 방법으로 풀면 시간 초과가 날 것이니(사실 문제 분류 봤음..) DP로 각 턴마다의 상태를 저장해 가면서 풀어야 할 것이다.

n번째 이동 때 어떤 칸(i,j)에 나이트가 존재할 확률을 p라 했을 때 n+1번째에 주변 8칸(나이트가 갈 수 있는)에 나이트가 존재할 확률은 모두 p/8이 된다.

이것을 N^2의 모든 칸에 대해 수행해주고 체스판을 벗어나는 경우는 무시하면 된다.

풀이 코드

import sys

input = sys.stdin.readline

dy = [2, 1, -1, -2, -2, -1, 1, 2]
dx = [1, 2, 2, 1, -1, -2, -2, -1]

def main():

    N, x, y, K = map(int, input().split())
    B = [ [0 for _ in range(N)] for _ in range(N) ]
    B[y-1][x-1] = 1

    for _ in range(K):
        temp = [ [0 for _ in range(N)] for _ in range(N) ]
        for i in range(N):
            for j in range(N):
                for d in range(8):
                    ny, nx = i + dy[d], j + dx[d]
                    if 0 <= ny < N and 0 <= nx < N:
                        temp[ny][nx] += B[i][j] * 0.125
                        
        B = temp
    print(sum(map(sum, B)))


main()