<백준 알고리즘>1526번 DP, 비트마스킹

접근 방법

100자리 수에 대하여 나타내야 하므로 그냥 반복문을 돌리기면 무조건 시간 초과나 나올 것 이라고 생각했다. 진짜 수에 대해서 다루는게 아니라 한자리씩 다룬다고 생각하면 100자리이므로 더 쉽게 문제에 접근하였다.

첫번째자리에 1-9까지의 수로 각각 시작하여 +- 1이 차이나는 수를 다음 자리의 수로 배치하는 방식으로 N자리 까지 백트래킹하여 접근한다.
이때 0부터 9까지의 수가 모두 사용되야 하므로 이 여부에따라 1이나 0을 반환한다.(백트래킹 하는 과정에서 어차피 계단식으로 수가 만들어지므로 이것은 고려할 필요가 없다.)
0-9까지 방문했는지를 표시하기 위해 비트마스킹을 사용하여 표시한다.
탑다운 방식으로 dp배열에 있는 수를 점점 반환하며 내려와 최종 결과에 하나씩 더해준다.

주의할 점

10억을 연산마다 나눠줘야지 답이 맞게 나왔다. 또한 중간에 갑자기 답이 음수로 떨어지는 경우가 있었는데 자료형을 int로 선언해서 오버플로우가 발생하여 음수로 떨어졌던 것이다. long long으로 바꿔준뒤에는 정상적으로 나왔다.

<느낀점>
dp문제는 생각보다 풀이 방식도 잘 안떠오르고 구현하기도 살짝은 까다로운 것 같다. 여러 문제를 풀어보며 좀 더 익숙해지면 좋을 것 같다.

코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>


using namespace std;

int N;

long long dp[10][101][1025] = { 0 };

long long dps(int curNum, int curCnt, int zeroToNine)
{
	if (dp[curNum][curCnt][zeroToNine]) return dp[curNum][curCnt][zeroToNine];

	if (curCnt == N)
	{
		if (zeroToNine == (1 << 10) - 1)
			return 1;
		else
			return 0;
	}
	

	if (curNum < 9) //1이 더 높을 경우 0는 10으로 넘어가므로 제외해줌
	{ 
		dp[curNum][curCnt][zeroToNine] = dps(curNum + 1, curCnt + 1,zeroToNine | (1 << (curNum + 1))) % 1000000000 
												+ dp[curNum][curCnt][zeroToNine] % 1000000000; // 바로 다음자리에서 가져온 값을 현재 dp에 저장해줌
	

	if (curNum > 0) //1이 낮을 경우 0은 -1이므로 제외 해줌
	{
	
		dp[curNum][curCnt][zeroToNine] = dps(curNum - 1, curCnt + 1, zeroToNine | (1 << (curNum- 1))) % 1000000000
												+ dp[curNum][curCnt][zeroToNine] % 1000000000;바로 다음자리에서 가져온 값을 현재 dp에 저장해줌
	}

	return dp[curNum][curCnt][zeroToNine]; //현재 dp를 바로 앞으로 반환
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    cin >> N;
	
	long long  ans = 0;

	for (int i = 1; i <= 9; i++)
	{
		ans = (ans + dps(i, 1, (1 << i))) % 1000000000;
	}

	cout << ans;

    return 0;
}