취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15488번 문제인 나이트가 체스판을 벗어나지 않을 확률이다.
문제는 아래 링크를 확인하자.

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

이동을 k번 한 뒤 좌표 (x1,y1)에 나이트가 있을 확률은 (이동을 k-1번 한 뒤 이 칸으로 올 수 있는 각 칸들에 도착할 확률) / 8을 합한 것과 같다는 점을 관찰하자.

위의 성질을 이용해 식을 세워 dp를 진행하는 것으로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long double ld;

int N, x, y, K;
ld board[51][50][50];

int dx[8] = { 1,2,2,1,-1,-2,-2,-1 };
int dy[8] = { 2,1,-1,-2,-2,-1,1,2 };

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> x >> y >> K;
	board[0][x - 1][y - 1] = 1;
	for (int i = 0; i < K; i++) {
		for (int x = 0; x < N; x++) {
			for (int y = 0; y < N; y++) {
				for (int k = 0; k < 8; k++) {
					int xx = x + dx[k], yy = y + dy[k];
					if (xx < 0 || xx >= N || yy < 0 || yy >= N) continue;
					board[i + 1][xx][yy] += board[i][x][y] / 8;
				}
			}
		}
	}

	ld ans = 0;
	for (int x = 0; x < N; x++) {
		for (int y = 0; y < N; y++) {
			ans += board[K][x][y];
		}
	}

	cout << fixed;
	cout.precision(20);
	cout << ans;
}