달려라 달려 이랴 이랴

풀이 처음엔 DFS로 접근했다. 문제는 경로의 최대가 2^63-1이란걸 잊고 있었다. 당연히 이정도 숫자면, count를 1씩만 올리는 dfs입장에서는 시간초과가 걸릴수밖에 없었다. 그럼 역시… 또DP문제. 문제를 DP시각으로 보려면… 오른쪽 사진처럼 생각해야한다. 큰문제는 0,0부터 2,2까지. 작은 문제는 (0,0-1,1), (1,1-2,2) 이렇게. 그럼이제 DP로 바라보는건 끝났다. 점화식을 만들 차례이다. dp[i,j]에는 0,0부터 i,j까지의 경우의 수들이 들어 있는게 이상적이다. 단 dp[2,2]에는 이미 1이란게 있어야한다. 그래야 1x1짜리 크기라면 바로 1이 나올수있게. 위 사진으로 예를 들자면 dp[2,1]에는 2,1에서 0으로 가는 길이있으니 dp[2,2]의 값을 가져오면 된다. ..