IT 개발 돼지의 일상

출처 : https://www.acmicpc.net/problem/2186 "전형적인 DP 문제, 재귀 호출 및 리턴에 대해 잘 알고있자." N,M 의 범위를 고려하면 100,000 개의 칸이 존재한다. 대략 계산해 봤을 때, 100*100 개 칸에서 갈 수 있는 방법의 개수는 4가지 방향에 최대 5칸의 거리 20개가 된다. 20^100,000 ... 브루트 포스로는 절대 돌아가지 않는다. 100 * 100 격자에 모든 문자가 'B' 이며 'BB' 를 만드는 경우의 수를 생각해보면 굉장히 많다. 그리디한 방법도 없고, 이럴 때는 DP 를 이용해 푸는 것이 좋겠다. 사실 이런 격자 문제를 풀때 DP를 사용하면 나는 항상 DP[X][Y][?] 이런 식으로 놓고 생각해본다. 무엇을 어떻게 메모이제이션 할 것인..