1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 정답률에 비해 어려웠던 문제였다. 비트마스크가 아직 익숙하지 않아서 그런지 비트마스크를 이용해서 메모이제이션을 어떻게 해야할지 고민하는데 시간이 오래 걸렸다. n번째 자리에 k라는 수가 오기 위해서는 n-1번째 자리에 k+1 혹은 k-1가 있어야 한다. 만약 비트마스크를 이용하지 않고 메모이제이션을 하면 다음과 같이 점화식을 세울 수 있다. dp[n][k] = dp[n-1][k-1] + dp[n-1][k+1] 그런데 이 문제에서는 해결해야하는 조건이 있다. 0부터 9까지 모든 수를 한번씩 사용해야 한다. 따라서, 0~9중에서 어떤 수를 사용했는가를 비트마스크를 이용하여 기록해야 ..
