noj.am/1562 백준 1562번 계단 수 문제이다. 문제) '계단 수'는 인접한 숫자간의 차가 모두 1인 수를 가리킨다. 자연수 N이 주어졌을 때, N자리 계단 수 중 0~9 모든 숫자가 등장하는 계단 수의 개수를 출력하세요. 풀이) 처음엔 N 이하인 모든 계단수의 개수를 계산하는 줄 알고 백트래킹을 생각했다. 그런데 문제를 다시 읽어보니 0~9 모든 숫자가 들어가야한다는 조건이 있어서 함수 인자로 used라는 set을 추가했다. 그럼에도 TLE(시간초과)가 나서 백트래킹으로 풀기 적합하지 않은 문제란 생각이 들었다. 백트래킹으로 계산하면 0~9가 모두 들어가지 못하는 케이스를 불필요하게 많이 체크하기 때문에 비효율이 발생한다. 문제에서 집중할 부분은 크게 3가지이다. "지금까지 결정한 자리(dig..