이 문제는 얼핏하면 dfs, bfs처럼 보여서 나도 처음에는 dfs로만 구현을 했었다. 하지만 dfs로 구현하면 값이 커질수록 반복되는 구간이 증가하기때문에 당연히 시간초과가 났었고 이를 고치기 위해 dp를 이용한 방법을 추가시켰다. 처음에는 dp를 어떻게 적용해야하는지가 감이 안와서 주변 친구들에게 도움을 받아서 이해를 하게 되었다. 이 문제를 시작점에서부터 도착점으로 가는 경로의 수를 구하는 문제에서, 임의의 점(x, y)에서 도착점 까지의 경우로 세분화 하여 구한다면, 그 어떤 경로로 (x, y)에 도착 하기만 해도 그 때부터의 경우의 수는 다시 구할 필요가 없다. 이 관점으로 코드를 구현해보자. 우선 처음에 dfs만 구현해서 시간초과가 난 코드이다. from sys import stdin as s..