각 칸에서 이동할 수 있는 칸으로 탐색해나가 도착점에 도달하면 그 이동 거리가 최소 거리가 되므로 bfs를 사용하면 빠르게 해결할 수 있다.
dfs로도 해결할 수 있지만 한번 방문한 칸은 다신 방문하지 않는 bfs와는 다르게 모든 경로를 탐색하므로 작동시간이 다소 오래걸린다.

두 방법 모두 다뤄보겠다.

처음 생각했던 방법은 dp[i]에 i원을 만들기 위한 동전의 최소 갯수를 저장하는 방식으로 현재 i보다 작은 j원을 순차로 돌며 i - j원 짜리 동전이 있나 확인한 후, dp[i]에는 그 중 가장 작은 값을 넣도록 작성했다.

단순한 dp문제다. 문제의 이동 조건에서 (r+1, c), (r, c+1), (r+1, c+1) 이렇게 3가지를 제시했지만, 사실 상 마지막 (r+1, c+1) 은 신경쓰지 않아도 된다.
왜냐하면 사탕의 갯수는 0 이거나 양수이기 때문에 더 많은 사탕을 가져와야 될 판에 굳이 대각선으로 가로질러 올 필요가 없기 때문이다.

그리디로 풀었을 때 최악의 경우 n * m * k번, 300 * 300 * 10,000 = 900,000,000번 계산하므로 시간초과가 난다.
그래서 dp로 풀어야 한다. 할 줄 알았는데 그리디하게 풀어도 맞는다고 한다.

가장 긴 증가하는 부분 수열 문제에서 dp[]에 길이를 넣었다면 지금 이 문제는 최대값을 넣으면 된다.

만약 i라는 숫자보다 j * j만큼 작은 수 인 i - j * j는 숫자 i의 제곱수의 최소항 갯수 - 1을 가질 것이다.
만약 j * j가 i와 같다면 j * j = i이므로 제곱수의 최소항 갯수가 한개가 된다.
이 과정을 j * j가 i보다 작거나 같을 때까지 반복해 가장 작은 값을 dp[i]에 넣고 i가 n만큼 돌면 dp[n]이 답이 된다.

각 자리수 별로 0 ~ 9까지 숫자들의 등장 가능한 빈도를 세면 된다.
dp로 풀 수 있고 바로 전 자리수에 자신보다 작거나 같은 수가 얼마나 있는지를 dp[i][j]에 저장해나가면 된다.

dp로 접근해서 풀어야 한다.
처음에 생각했던 방법은 dp[i]에 i원을 만들 수 있는 경우의 수를 저장하고, 각 dp[i]에 가지고 있는 동전의 종류(arr[j])원을 뺀 dp[i - arr[j]]를 더해주는 방법으로 풀면 되겠다고 생각했다.

보자마자 떠오른것은 조합이다.
mCn을 계산하면 정답이 나오지만 m이 최대 29까지 등장하기 때문에 계산 과정에서 29!을 계산할 여지가 있다.
29!은 long long에도 못들어가는 아무튼 엄청 크다.
이를 해결하는 방법은 여러가지가 있다.

동적 계획법으로 해결할 수 있다.