반응형
1562
-
BOJ) 계단 수 (1562 번)알고리즘/백준 2021. 3. 7. 17:19
계단 수 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 45656, 1210123 과 같이 각 자릿 수의 차이가 1씩 나는 수를 계단 수라고 한다. 자릿 수를 의미하는 n이 주어질 때, 이러한 계단수가 몇 개 존재하는지 구하는 문제다. 이 때, 모든 계단 수는 0으로 시작하지 않는다. DP와 비트 마스크를 활용해서 푸는 문제로, 각 자릿수, 0 ~9의 수, 비트마스크를 저장할 3차원 정수형 배열 DP를 이용해서 풀었다. 우선, n = 1인 경우, 0 ~ 9는 각각 자신 수 하나를 가진다. 이를 비트마스크로 표현해주면서, n을 증가시켰다. 0인 경우에는 0으로 시작할 수 없기 때문에, 0다음에 올 수 있는 수인 1만 dp에 추가시켜..