1562. 계단 수

예전부터 북마크만 해놓던 문제. 한 두달 됐나?

1562번: 계단 수

---

10844. 쉬운 계단 수를 강화한 문제이다.

 

10844번에서는 아주 간단한 2차원 DP로 풀 수 있었다. 다음과 같이 정의하면 된다.

$dp[i][j]$: 길이가 $i$이고 $j$로 끝나는 계단 수의 개수

 

그런데 1562번 문제에서는 0부터 9까지의 숫자가 적어도 한 번 등장해야 한다는 조건이 있다. DP를 이렇게 정의해 보자.

$dp[i][j][k]$: 길이가 $i$이고 $j$로 끝나며, 비트마스크가 $k$인 계단 수의 개수

 

여기서 $k$는 10자리의 비트마스크이다. 어떤 수에 $i$가 들어 있다면 $k\&(1<<i)$는 0이 아니다. 이제 10844번의 사고방식을 대입하면 다음과 같이 $dp[i][j][k]$를 계산할 수 있다.

$dp[i][j][k] = dp[i-1][j+1][k]~+~dp[i-1][j+1][k~XOR~(1<<j)]~+~$

$dp[i-1][j-1][k]~+~dp[i-1][j-1][k~XOR~(1<<j)]$

 

어떤 수의 맨 끝 자릿수가 $j$일 때, 계단 수의 정의에 따라 $i-1$번째 자리에는 $j+1$ 또는 $j-1$이 올 수 있다. 이때 $i-1$번째 자리까지 $j$가 있는 경우와 없는 경우를 모두 더해야 한다. $j$가 없는 경우에는 $k$에서 $j$에 대응되는 비트를 $XOR$ 연산으로 지워서 접근해야 한다.

 

# 맞왜틀 (펼치기)

다음의 함수는 비트마스크 ``bit``의 ``i``번째 비트가 켜져 있는지 검사하는 함수이다.

bool contains(int bit, int i)
{
	return bit & (1 << i) != 0;
}

그런데 &보다 !=의 우선순위가 더 높기 때문에 이 함수는 예상과 다른 동작을 하게 된다. 따라서 뒷부분의 ``!= 0;``을 지우거나, & 연산하는 부분을 괄호로 감싸줘야 한다. 불안하면 그냥 괄호 치자.

 

이거 하나때문에 3시간 썼다. 하..

---

묵혀놨던 문제 해결!