[BOJ / 다차원 비트마스크 DP] 1562 계단 수

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

1562번: 계단 수

 

1562 계단 수

알고리즘 : 다차원 비트마스크 DP

정답률이 47%로 나오고 있지만 쉬운 문제는 아닙니다.. 힌트로 정답을 확인할 수 있기 때문에 정답률이 높은 것 같습니다.

4차원 배열을 활용 한 DP이며 dp[A][B][C][D]에서 각각

 

                                    - A : 현재 계단 수의 길이 <= 100

                                    - B : 지금 현재 보유중인 수의 상태를 나타내는 비트마스크 < 2^10

                                    - C : 현재 수의 가장 앞자리를 나타내는 수  < 10

                                    - D : 현재 수의 가장 뒷자리를 나타내는 수 < 10

 

입니다. 기저로 길이 1~2까지의 dp배열을 채워넣고

bottom-up 방식을 활용하여 길이 3부터 채워넣습니다. 앞 자리 수가 0인 계단 수는 정답으로는 취급하지 않지만 1 ~ 0123 ~ 2 처럼 그 다음 길이에서는 자식으로 활용될 수 있기 때문에 앞자리 수가 0인 배열도 채워넣어야 합니다. 비트마스크를 활용해 어떤 수에 0부터 9까지 수가 있는지 체크할 수 있어야 하며 이를 활용하여 풀이하면 됩니다.

 

 

 

 

 

 

 

 

 

< CODE >

#include <iostream>
#include <algorithm>
#include <cstdlib>

using namespace std;

#define MAX 105
#define MOD 1000000000

typedef long long int ll;

ll dp[MAX][1<<10][10][10];
ll result = 0;
int complete = (1 << 10) - 1;

int addTwoBit(int a, int b)
{
	int ret = 0;
	ret |= (1 << a);
	ret |= (1 << b);
	
	return ret;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	
	cin >> n;
	
	for(int i = 0; i <= 9; i++)
	{
		dp[1][1 << i][i][i] = 1;
		
		for(int j = i - 1; j <= i + 1; j += 2)
		{
			if(j == -1 || j == 10)
				continue;
			
			int temp = addTwoBit(i,j);
			
			dp[2][temp][i][j] = 1;
		}
	}
	
	for(int len = 3; len <= n; len++)
	{
		for(int i = 0; i <= 9; i++)
		{
			for(int j = 0; j <= 9; j++)
			{								
				for(int bit = 1; bit < (1 << 10); bit++)
				{
					int f[4] = {i - 1, i - 1, i + 1, i + 1};
					int l[4] = {j - 1, j + 1, j - 1, j + 1};
					
					for(int k = 0; k < 4; k++)
					{
						if(f[k] == -1 || f[k] == 10 || l[k] == -1 || l[k] == 10 || \
						   dp[len - 2][bit][f[k]][l[k]] == 0)
							continue;
						
						int nBit = addTwoBit(i,j) | bit;

						dp[len][nBit][i][j] += dp[len - 2][bit][f[k]][l[k]];
						dp[len][nBit][i][j] %= MOD;

						if(nBit == complete && len == n && i != 0)
						{
							result += dp[len - 2][bit][f[k]][l[k]];
							result %= MOD;
						}
					}
				}
			}
		}
	}
	
	cout << result << '\n';
	
	return 0;
}

시간 : 112ms

 

태그 : #BOJ 1562 #BOJ 계단수 #계단수풀이 #백준 1562 #백준 계단수