그럼, 오늘도 역시 세준이는 0부터 9까지 모든 한 자리수가 자리수로 등장하면서, 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N이면서 0에서 9가 모두 등장하는 계단 수가 총 몇 개 있는 지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
예제
풀이
메모이제이션을 활용한 DFS로 해결하였습니다.
그냥 DFS로만 풀었을 때는 시간 초과가 발생합니다.
메모이제이션에서 숫자가 아닌 자릿수와 비트 마스크만 저장한 이유는 자릿수와 비트 마스크만 같다면 다른 숫자이어도 다음에 탐색될 결과가 같기 때문입니다.
추가로 10자릿수 미만의 숫자에선 조건에 해당하는 숫자가 없기 때문에 예외 처리하였고 0b로 시작하는 숫자는 2진수이기 때문에 활용하여 문제를 풀었습니다. (2진수 : 0b, 8진수 : 0, 16진수 : 0x)
풀이과정은 다음과 같습니다.
입력받은 자릿수가 10 미만일 경우 0을 출력하고 종료한다.
10 이상일 경우엔 메모이제이션을 활용한 DFS로 탐색한다
탐색할 숫자의 처음 자리의 숫자부터 입력하여 탐색하며, 0으로 시작하는 숫자는 없기 때문에 1부터 탐색한다
탐색은 DFS를 활용해서 진행한다. 올라갈 때 와 내려갈 때 두 가지 상황으로 진행하고, 숫자 범위에 대한 예외처리를 해준다.
탐색 중 이미 탐색을 진행했던 자릿수와 비트 마스크라면 탐색 결과를 반환하고 종료한다.
성공 코드
#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;
//define
using ull = unsigned long long;
using location = pair<int, int>;
using matrix = vector<vector<int>>;
using dp = vector<vector<vector<int>>>;
const int LIMIT = 1000000000;
//custum function
int DFS(int lastNum, int bitMask, int target, dp &DP, int place = 1)
{
int result = 0;
//목표 자릿수에 도달 했다면 조건에 맞는지 확인
if (place == target)
{
return bitMask == 0b1111111111;
}
//이전에 탐색했던 상황이라면 해당 값 반환
if (DP[place][lastNum][bitMask] != -1)
{
return DP[place][lastNum][bitMask];
}
//내려갈때와 올라갈 때
int routes[2] = { -1, 1 };
for (auto route : routes)
{
int nextNum = lastNum + route;
if (0 <= nextNum && nextNum <= 9)
{
result = (result + DFS(nextNum, bitMask | (1 << nextNum), target, DP, place + 1)) % LIMIT;
}
}
return DP[place][lastNum][bitMask] = result;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
////////////////////////////////////
//DFS로 탐색을 한다.
//단 이전에 탐색했던 상황(자릿수, 맨 뒷자리, 비트마스크)이라면 해당 결과를 반환한다
//Declaration
int target(0), answer(0);
cin >> target;
//Solution
//10의 자리 미만에선 조건에 맞는 숫자가 나올 수 없다.
if (target < 10)
{
//Output
cout << "0\n";
}
else
{
//메모이제이션용 배열
dp DP = dp(101, vector<vector<int>>(10, vector<int>(1 << 10, -1)));
//맨 앞자리 부터 시작하여 숫자를 만들어 갔을 때 조건에 맞는 숫자를 탐색
//맨 앞자리가 0인 숫자는 없으므로 1부터 시작
for (int digit(1); digit < 10; ++digit)
{
answer = (answer + DFS(digit, 1 << digit, target, DP)) % LIMIT;
}
//Output
cout << answer << '\n';
}
return 0;
}
