[BOJ]1562번: 계단 수

 

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

---

jason님 풀이를 참고해서 해결하였습니다. (https://jason9319.tistory.com/135)

 

dp + bit masking을 통해 해결할 수 있습니다.

 

계단 수를 완성하는데 0~9 까지 모든 수를 사용해야 합니다. 

이는 비트로 표시하여 (1 << 0) 부터 (1 << 9)에 해당하는 모든 비트가 1이면 조건을 만족하게 됩니다.

 

점화식을 살펴보자면

자릿수가 N이 될 때 까지 계단수 조건을 만족시키며 확장합니다.

 

dp[pos][num][state]: 완성한 자릿수가 pos, 현재 숫자는 num, 0~9 포함상태는 state일 때 계단 수의 갯수

 

<점화식>

dp[pos][num][state] = dp[pos+1][num+1][state | (1 << num+1)] + dp[pos+1][num-1][state | (1 <<num-1)]

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1562.cc