rlagusrl0606   7달 전

어떻게 게임판 최대 크기가 100인데 최대 경로갯수는 2의63승 -1 까지 나올 수 있나요?

가장 많이 경로가 나오려면 해봤자 게임판 모든 칸의 점프 숫자가 1인 경우일 것 같은데

정말 신기하네요

luckyandykang   7달 전

N이 100이고 마지막 칸이 아닌 모든 칸에 1이 적혀 있는 경우, 원하는 순서대로 이동할 수 있으므로 경로의 수는 198 C 99 = 2.27 * 10^58 정도입니다.

실제 입력으로는 답이 이보다 훨씬 작은 경우만 주어질 뿐입니다.

rlagusrl0606   7달 전

아 감사합니다.
제가 n이 4인 상태에서 다 1로 넣고 해봤더니 20정도만 나오길래 100까지 가더라도 많지 않겠는데 생각했더니 기하 급수적으로 늘어나는군요
항상 생각을 깊이 해보겠습니다

pkearth   7달 전

경로의 개수가 263-1보다 작거나 같다는 것은 경로의 개수가 263-1인 경우가 존재한다는 것과는 다릅니다.

luckyandykang   7달 전

이것도 맞네요. 답의 상한이 아무리 작아도, 저렇게 표현하는 데에는 문제가 없습니다.

댓글을 작성하려면 로그인해야 합니다.