목록백준 15488 c++ (1)

1일1알

백준 15488번 나이트가 체스판을 벗어나지 않을 확률 C++ (골드5)

https://www.acmicpc.net/problem/15488 dp테이블을 [행][열][움직일 수 있는 횟수]로 정하고 똑같은 행,열, 움직일 수 있는 횟수를 2번이상 탐색한다면 기존에 구해놓은 값을 바로 반환하는 메모이제이션 방식을 사용하였다. 나이트가 다음에 가있을 칸을 계산하고 움직일 수 있는 횟수를 1씩 줄이면서 탐색해나간다.1. 만약 나이트가 체스판 밖에있다면 0을 반환한다.2. 만약 나이트가 방문한 [행][열][움직일 수 있는 횟수] 가 이전에 탐색된 기록이 있다면 그 값을 바로 반환한다.3. 만약 k가 0이면 더이상 움직일 수 없고, 체스판 안쪽에 있기 때문에 1을 반환한다. 나이트가 움직일 수 있는 방향은 8방향이기때문에 8방향에 대해 탐색을 진행한 값을 8로 나누고 캐시 테이블에 저..
알고리즘 2024. 6. 1. 11:06
이전 Prev 1 Next 다음