요구사항이 정확하지 않아서 모르겠는데 지갑 떨어트린 곳까지 가는 경우의 수 * (어떤 지점에서 돌아가야 함이 명시되어 있을 때) 어떤 지점에서 지갑 떨어트린 곳 까지 가는 경우의 수 * 지갑 떨어트린 곳에서 목표지점까지 도달하는 경우의 수

이렇게 3개 곱하면 되지 않나요? 물론 테이블은 3번 다 따로 계산해야 되고요

간단하게 말씀드리면 최단거리중 중간에 (꼭)1번 딱'한'칸 왔던길 뒤로 갔다가 오는 문제입니다

음 그럼 일단 모든 점까지 가는 경우의수 테이블을 만들고(여기서 한번 뒤로갔다왔다 치고) 거기서 또 목적지까지 가는 경우을 일일히 곱해서 다 더해주면 될거같기도 하네요 한번 시도해보겠습니다 

근데 또 마지막 지점에 갔다고 했을때 왼쪽으로 갔다가 오는 경우와 위쪽으로 갔다 오는 경우가 나뉘는데 이런 방식이라면 마지막까지 가는경우의수x마지막에서 마지막으로가는 경우의수? 하면 뭔가 모순이 생기는 느낌입니다 ..

일단 아이디어 제시 감사드립니다 ㅜ

두 가지 풀이가 있습니다.

1. 되돌아가는 경우를 따로 생각하지 말고, 갔다가 되돌아오는 것을 하나로 생각합니다. 그러면 6x6에서 어떤 곳에서 "갔다가 되돌아올지" 정합니다. 그렇게 36개의 경우에 대해 (0,0에서 n,m으로 가는 경우) * (아래가 비었는지 오른쪽이 비었는지에 따라 0에서 2사이) * (n,m에서 5,5로 가는 경우)를 곱합니다.

그러면 4620이 나옵니다.

2. 6x6에서, 오른쪽에서 2번째 지점까지 갈 수 있는 경우의 수를 계산합니다.

최상단의 줄에서 오른쪽 2번째까지 갈 수 있는 경우는 1개가 있고 5개의 지점을 거쳐왔으므로 오른쪽으로 갔다가 되돌아오는 경우가 5개 있습니다.

그래서 1 * 5

다음줄은 5 * 6

다음줄은 15 * 7

다음줄은 35 * 8

다음줄은 70 * 9

다음줄은 126 * 10

총합 2310

똑같이 아래 방향으로도 해주면 2310이 나오므로 총합 4620이 나옵니다.

감사합니다 이해가 되었습니다. 2번째방법은 조금 특이하네요

알고리즘을 짜기도 간단해 보이긴하는데

혹시 2번째 방법에서 오른쪽 2번째까지 가는 방법*그전에 왓다갔다할수있는점(가로,세로따로) 로 구하셨는데 그 다음에 목적지까지 갈수있는경우가 또 여러개일수 있는데 이걸 안곱해서 구해진게 맞을까요? 예를들어 (5,2)까지 가는 방법이 5개 그리고 거기까지 가는 점의개수가 6개 여서 5~6을 한 후 여기서 목적지까지 갈수있는 방법은 또 5가지가 되는것 같습니다 .. 

2번째 방법에서 마지막에 목적지로 가는 수는 1가지입니다. 아래를 거쳐 가는것은 이미 밑에서 셌기 때문에 무조건 오른쪽으로밖에 못 갑니다.

감사합니다 이해했습니다!