문제

• 
• 시간 제한: 2초
• 메모리 제한: 128MB

Problem Analysis

N 자리의 수가 k인 경우는 N-1자리의 수가 k-1, k+1인 경우로부터 만들어진다. 이렇게 문제를 쪼개서 풀 수가 있는데, sub-problems이 반복되기 때문에 Dynamic Programming 으로 풀 수 있을 것으로 보인다.

Algorithm

위와 같은 Top-Down 기반에서, N이 1일 때부터 풀도록 하여, Bottom-Up 방식으로 푼다. 이때, 현재 0~9 중에서 무엇을 사용했는 지도 저장해 주어야 한다. 0~9를 사용하는 방법에는 2^10가지 경우가 있으므로, 0~1023을 이진수로 index로 잡아서(BitMasking), 해당 index에 경우의 수를 저장해 주면 된다.

Data Structure

• DP[N][10][1024]: index( N 자리, 현재 k인, 0~9 사용 여부)에 해당 경우의 수 저장

결과

Other