[백준 1562번] 계단 수 (java)

1562번: 계단 수

 

 

문제 정답률에 비해 어려웠던 문제였다. 비트마스크가 아직 익숙하지 않아서 그런지 비트마스크를 이용해서 메모이제이션을 어떻게 해야할지 고민하는데 시간이 오래 걸렸다.

 

n번째 자리에 k라는 수가 오기 위해서는 n-1번째 자리에 k+1 혹은 k-1가 있어야 한다.

만약 비트마스크를 이용하지 않고 메모이제이션을 하면 다음과 같이 점화식을 세울 수 있다.

dp[n][k] = dp[n-1][k-1] + dp[n-1][k+1]

 

그런데 이 문제에서는 해결해야하는 조건이 있다. 0부터 9까지 모든 수를 한번씩 사용해야 한다.

따라서, 0~9중에서 어떤 수를 사용했는가를 비트마스크를 이용하여 기록해야 한다.

비트마스크의 각 자리는 특정 숫자를 사용했는지 아닌지를 나타낸다.

0부터 9까지 총 10개의 숫자를 확인해야 하므로 비트마스크의 자릿수는 총 10개이다.

 

예를 들어, 1,2,3을 사용했다면 0000001110(2)로 나타낼 수 있다.

0부터 9까지 모든 수를 한번씩 사용했다면 1111111111(2)가 된다.

 

비트마스크를 이용하여 모든 수를 한번씩 사용했는지 확인해야 하기 때문에 dp 배열을 3차원 배열로 생성하여 비트마스크 정보를 나타내는 인덱스를 만들어준다.

dp[n][k][visit | (1<<k)] = dp[n-1][k-1][visit] + dp[n-1][k+1][visit]

 

dp[n][k][visit] : n번째 자리에 k가 있고, visit에는 여태까지 사용한 수의 정보가 있음

 

그렇다면 마지막 N번째 자리까지 계단수를 완성했을 때, 모든 수를 다 사용한 경우(1111111111(2))를 카운트하려면 dp[N][0][1111111111(2)]부터 dp[N][9][1111111111(2)]까지 더하면 된다.

 

 

전체코드 :