1562번: 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
비트마스킹, 다이내믹 프로그래밍, 재귀+메모, 분할 정복이 모두 들어있는 좋은 문제다.
위의 그림은 문제의 내용을 표현한다. 계단 수여야 하므로 이전보다 하나 작거나 큰 수가 이번에 온다.
- 맨 위의 123454의 경우에는 그 다음에 3,5 두 개의 수가 올 수 있다. 즉, 2가지로 갈래가 나눠진다.
- 789 다음에는 8만 가능하다
- 3210 다음에는 1만 가능하다.
여기까지 파악된 것은 N자리의 숫자를 만들어야 하고, 현재 수를 알면 다음 수가 뭐가 되는지 알 수 있다는 점이다.
이제 중요한 것은 0부터 9까지 모든 숫자가 나왔는지이다. N자리의 숫자를 만드는 계단 수는 한두 개가 아니다. 그렇다면 매번 0부터 9까지 루프를 돌며, 해당 숫자가 등장했는지 안 했는지 확인할 수는 없다. 여기서 바로 비트마스킹이 힘을 발휘한다.
비트마스킹은
어떤 옵션들이 선택되었는지 한 번에 확인하고자 할 때,
어떤 정점들을 거쳤는지/방문했는지 한번에 확인할 때,
어떤 물건들을 챙겼는지 한번에 확인할 때,
등과 같이, 어떠한 선택 옵션이나 필요 준비물(?)등이 선택되었는지, 방문했는지 등을 단 한 번의 연산으로 확인할 수 있게 해 준다. 옵션이나 준비물의 개수가 30개 이하 정도일 경우, 이 방법을 의심해볼 필요가 있다. 사실 조금 더 많아도 2개 이상의 마스크를 준비해서 관리해줄 수도 있다. 이번 문제에서는 0부터 9까지 이므로 옵션은 10개인 것이다.
위의 그림에서 0101010110이라는 파랑 수를 보자. 이것은 어떤 수가 선택되었는지를 나타내는 비트 마스크이다. 아래에 있는 주황색 숫자와 비교했을 때, 파랑 수는 현재 8,6,4,2,1을 갖고 있음을 알 수 있다.
이쯤 되면 감이 오겠지만, 비트마스킹을 사용하면 시간 뿐만 아니라 공간(메모리)에서도 큰 이득을 볼 수 있다. 왜냐하면 0부터 9까지의 숫자를 방문 체크 등으로 배열 관리하지 않고, 단 하나의 int에 비트만 조작하여 관리하고 있기 때문이다.
bool visited[10]에서 int mask가 된 것이다.
그리고 0부터 9까지 모두 선택되어 있어야 하므로, 가장 마지막에 모든 10개의 비트가 켜져 있을 때의 값인 1023과 같은지만 확인하면 되는 것이다.
이제 N자리의 숫자를 만들어야 한다는 점, 현재 수를 알면 다음 수가 뭐가 되는지 알 수 있다는 점에 이어, 마스크 관리를 통해 0부터 9까지 모두 등장했는지를 확인하는 방법까지 알았다.
이제 다이나믹 프로그래밍 등을 적용할 준비가 다 되었다. 이제 어떻게 기록할 것인지를 고민하면 되는데 필자는 위의 그림과 같이 기록하였다.
i는 1에서 시작해서 n까지 증가하는 각 자릿수를 나타낸다.
m은 현재 i번째 자리에 있는 숫자가 무엇인지를 나타낸다.
그리고 마지막 k는 현재 어떤 숫자들이 등장한 상태인지를 한눈에 볼 수 있는 마스크이다.
그러면 이제 현재수(m)가 0이면 다음에는 1을 넣어주고, 9면 다음에는 8을, 그 외에는 2가지 경우로 나눠서 생각해야 한다.
필자는 재귀 함수를 만들 때, 논리대로 또는 그냥 생각하는 대로 짜면 되는 경우가 많았다. 이번에도 마찬가지다. 쉽다는 말이 아니니 오해하지는 마시길 바란다. 생각하는 대로 적어나간다는 의미이다.
아래의 코드를 보자.
// 재귀함수 counter
int counter(int i,int m,int k){
// 현재 0이면 다음은 1
if(m==0)memo[i][m][k]=counter(i+1,1,k|(1<<1));
// 현재 9면 다음은 8
else if(m==9)memo[i][m][k]=counter(i+1,8,k|(1<<8));
// 그렇지 않으면 m-1과, m+1로 나누어 진행하고 결과를 합산해준다.
else{
memo[i][m][k]=(counter(i+1,m-1,k|(1<<(m-1)))
+counter(i+1,m+1,k|(1<<(m+1))))%mod;
}
return memo[i][m][k];
}말 그대로 써주면 된다. 0이나 9가 아니면 2갈래로 나누어(재귀 함수 2개로) 각자 구하고 그 결과를 합해주면 되는 것이다.
그리고 memo배열 안에 결과를 기록하여(메모이제이션), 같은 연산을 반복하지 않도록 한다. (피보나치에서 기록을 통해 시간복잡도를 크게 줄이는 것과 같은 원리이다.)
<주요 내용>
분할 정복, 다이나믹 프로그래밍, 재귀함수, 메모이제이션, 비트마스킹, 비트 연산
<코드>
설명은 재귀 함수, 메모이제이션, 분할 정복 등이 포함된 코드에 대해서였다.
그 아래는 다이나믹 프로그래밍으로 풀이한 코드도 같이 첨부하였다. 큰 내용은 동일하니 그 코드에 대한 설명은 생략하였다.
또한, 나머지 연산에 주의한다.
#include <iostream>
#define endl '\n'
using namespace std;
const int mod=1e9;
const int v=1023;
int n,ans,num;
int memo[101][10][1<<10];
int counter(int i,int m,int k){
if(memo[i][m][k])return memo[i][m][k];
if(i==n && k==v) return 1;
else if(i==n && k!=v)return 0;
if(m==0)memo[i][m][k]=counter(i+1,1,k|(1<<1));
else if(m==9)memo[i][m][k]=counter(i+1,8,k|(1<<8));
else{
memo[i][m][k]=(counter(i+1,m-1,k|(1<<(m-1)))
+counter(i+1,m+1,k|(1<<(m+1))))%mod;
}
return memo[i][m][k];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for(int k=1;k<10;++k)ans=(ans+counter(1,k,1<<k))%mod;
cout<<ans<<endl;
return 0;
}
#include <iostream>
#define endl '\n'
using namespace std;
const int mod=1e9;
int ans,temp,dp[100][10][1<<10],n;
int addmod(int a,int b){
int amod=a%mod;
int bmod=b%mod;
if (!amod) {
return bmod;
}
if (!bmod) {
return amod;
}
if (amod+bmod<=amod) {
return (amod-(mod-bmod))%mod;
}
return (amod+bmod)%mod;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin>>n;
for(int i=1;i<10;++i)dp[0][i][1<<i]=1;
for(int i=1;i<n;++i){
for(int j=0;j<10;++j){
for(int k=0;k<(1<<10);++k){
if(!j){
if(dp[i-1][j+1][k]){
temp=k|(1<<j);
dp[i][j][temp]=addmod(dp[i][j][temp],dp[i-1][j+1][k]);
}
}else if(j==9){
if(dp[i-1][j-1][k]){
temp=k|(1<<j);
dp[i][j][temp]=addmod(dp[i][j][temp],dp[i-1][j-1][k]);
}
}else{
if(dp[i-1][j+1][k]){
temp=k|(1<<j);
dp[i][j][temp]=addmod(dp[i][j][temp],dp[i-1][j+1][k]);
}
if(dp[i-1][j-1][k]){
temp=k|(1<<j);
dp[i][j][temp]=addmod(dp[i][j][temp],dp[i-1][j-1][k]);
}
}
}
}
}
for(int i=0;i<10;++i)ans=addmod(ans,dp[n-1][i][(1<<10)-1]);
cout<<ans<<endl;
return 0;
}
