뱀과 사다리 게임

클래식 보드게임인 뱀과 사다리 게임을 한다. 10×10 보드에서 1번 칸에서 시작해 100번 칸에 도달하면 이긴다.

매 턴마다 주사위(1~6)를 굴려 해당 칸 수만큼 앞으로 이동한다. 사다리가 있는 칸에 도착하면 사다리 위쪽 칸으로 이동하고, 뱀이 있는 칸에 도착하면 뱀의 꼬리 칸으로 이동한다. 이동 후 100번 칸을 초과하면 이동하지 않는다.

1번 칸에서 출발하여 100번 칸에 도달하기 위한 주사위 최소 횟수를 구하시오.