[Java] 백준 1562 (계단 수) Gold 1

Problem : https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net Approach Bitmasking을 이용한 DP문제였다. 그냥 계단수를 구하는 문제를 풀어본 기억이 있어 일단 DP를 떠올렸다. 그리고 보통 사용한 숫자를 체크할 때에는 Bitmasking을 사용했기에 이 문제도 그렇게 접근해 보았다. i자리 계단수를 구하는 방법은 i-1자리 계단수의 끝자리에 +1 한 숫자와 -1 한 숫자를 붙인 계단수의 합이다. 하지만 끝자리가 0과 9인 경우에는 각각 +1한 숫자, -1한 숫자만 고려해야한다. 34가 계단수임을 알고 있으면 343도(-1한 숫자를 붙인 것) 계단수..