백준 1562. 계단 수

https://www.acmicpc.net/problem/1562

1562번: 계단 수

 

이 문제는 아래 쉬운 계단 수와 dp 점화식은 같다.

 

https://tose33.tistory.com/89

백준 10844. 쉬운 계단 수

 

하지만 이 문제는 bit 연산을 써야지만 풀린다.

 

이전 쉬운 계단 수 에서 점화식은 d[i][j] 배열을 만들고 i 는 숫자의 길이, j 는 마지막 숫자라고 했을때

d[i][j] = d[i-1][j-1] + d[i-1][j+1] 이었다. (물론 끝자리가 0,9 일때는 제외하고)

예를들어 123 이면 다음에는 1234 or 1232 이런 식으로 추가 해주기만 하면 되기 때문이다.

 

그런데 이 문제는 0~9 가 무조건 포함 되야한다.

따라서 사용한 숫자들이 뭔지 알아야 한다는 뜻이다. 

 

d[i][j][bit] i 는 길이, j 는 마지막 숫자, bit 는 사용한 숫자

예를들어 bit=101 이면 2,0 숫자를 사용했다는 의미다.

bit 의 최대 크기는 숫자가 0~9 로 총 10 개 이므로 1<<10 (10000000000) 일 것이다.

 

이제 점화식은 기본적으로 쉬운 계단 수랑 비슷한데, 이전 크기의 숫자와 현재 크기의 숫자의 비트를 or 연산 해줘야 한다.

or 연산 해주는 이유는 예를들어 이전 크기 숫자의 bit 가 101 이라고 해보자.

101 은 2,0 숫자를 사용했다는 뜻이다.

 

그리고 현재 크기 숫자에서 뒤에 1을 추가 한다고 해보자.

연산은 (1<<1) = 10 이 된다.

101 | 010 = 111 

111 은 2,1,0 을 사용했다는 뜻이 된다.

 

이렇게 or 연산으로 쉽게 기존에 사용했던 숫자들에 이번에 사용한 숫자를 추가로 표시할수 있다.

 

최종적으로 답은 N 크기 숫자의 0~9 로 끝나는 경우 중, bit 가 1111111111 즉 모든 숫자를 사용한 경우를 모두 더해주면 된다.