📎 문제 출처
https://www.acmicpc.net/problem/10844
📌 문제 설명
❓ 풀이 방법
처음에는 아래와 같이 dfs를 생각했다. 시작노드에서 +1 또는 -1 한 수로의 탐색을 한것이다.
하지만 시간초과가 떴고 해결한 방법이 동적 프로그래밍(DP)이다.
이차원 dp 테이블을 사용한 것은 처음이라 이해하는 데에 시간이 많이 걸렸다.
dp[i][j] : i번째 자리에 숫자 j가 오는 숫자의 수라고 했을 때
i가 1일때, 즉 1의 자리에 숫자 j가 오는 경우의 수는
dp[1][1] = dp[1][2] = ... = dp[1][9] = 1
또, i가 2일 때, 두번째 자리에 숫자 1이 오는 경우의 수는 첫번째 자리에 0 또는 2가 오는 경우를 더한 것이므로
dp[2][1] = dp[1][0] + dp[1][2] = 1 + 1 = 2
이제 일반화를 통해 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]라는 점화식을 구할 수 있다.
📌 Code
