[백준 C++] 1562 계단수

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

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

풀이

일반적인 DFS로 푼다면 대략 2^100만큼의 연산이 필요해진다.
따라서 좀더 효율적으로 해결하기위해,
DP[자릿수][현재숫자][사용된숫자비트필드]로 DP를 돌리면
100 10 2^10 = 백만회의 연산만으로 해결할 수 있다.
즉,

• 일반적인 DFS로 푼다면 0번째부터 가능한 모든 경우의수를 가지 뻗듯 전부 따지는것으로 2^100만큼의 연산이 필요하나,

• DP를 이용하면 똑같이 0부터 N까지 i를 늘려갈때 i번쨰 상태로 가능한 상태를 DP테이블의 차원하나하나로 특정시켜서 바로직전 i-1번째 DP테이블값을 이용해 현재 DP[i]를 구하기에 앞서 본 DFS의 불필요한 가지들이 제거된채 연산을 수행하게 되는, 100만회의 연산만에 해답을 구할 수 있게되는것이다.
  이때 i또한 0부터 N까지 하나씩 늘려가며 살펴본다.

이처럼 이 문제는 DP를 bottom-up방법으로 구현해보았다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
#define mp std::make_pair 
#define mt std::make_tuple
#define dq std::deque
#define pq std::priority_queue
#define sw std::swap
#define ts(x) std::to_string(x)
#define tc() c_str()
#define sc(x, ...) scanf(x, ##__VA_ARGS__) 
#define pr(x, ...) printf(x, ##__VA_ARGS__) 
#define ins(x) insert(x)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define PB() pop_back()
#define PF() pop_front()
#define ph(x) push(x)
#define TT() top()
#define PP() pop()
#define BB() back()
#define FF() front()
#define cls() clear()
#define emp() empty()
#define len(x) x.length()
#define sz(x) ((int)x.size()) //컨테이너에서 사용
#define ms(a) memset(a, 0, sizeof(a)) //0으로 초기화
#define rep(i, n) for(int i = 0; i < n ; i++)
#define rrep(i, r, n) for(int i = r; i < n ; i++)
#define rrrep(i, r, n) for(ll i = r; i < n ; i++)
#define _rrep(i, r, n) for(int i = r; i >= n; i--)
#define _rrrep(i, r, n) for(ll i = r; i >= n; i--)
#define each(x, a) for (auto& x: a)
#define all(x) x.begin(),x.end() //STL에서 전체 처리할때 사용
#define range(x, r, n) x.begin() + r, x.begin() + n //STL에서 구간설정
#define ct continue
#define br break
#define rt return
#define _TYF typedef //코드줄이기
#define _UG using
#define _TCE template <class T> inline
//#define MAX 
const int IMAX = INT32_MAX; const int IMIN = INT32_MIN;
const long long LMAX = LLONG_MAX; const long long LMIN = LLONG_MIN;
const long double PI = 3.141592653589793238462643383279502884197;
_UG std::vector; _UG std::stack; _UG std::queue; _UG std::tuple; _UG std::set; _UG std::list; _UG std::bitset; _UG std::string; _UG std::pair; _UG std::greater;
_UG std::tie; _UG std::sort; _UG std::max_element; _UG std::min_element; _UG std::fill; _UG std::stoi; _UG std::stod; _UG std::stof; _UG std::stol; _UG std::stold; _UG std::stoll; _UG std::stoul; _UG std::stoull; _UG std::to_string;
//_UG std::max; //_UG std::min; //_UG std::map;
_TYF long long ll;// _TYF unsigned long long ull; // 입출력오류날때가있음.
_TYF pair<int, int> pii; _TYF pair<double, int> pdi; _TYF pair<int, double> pid; _TYF pair<double, double> pdd; _TYF pair<int, ll> pil;
_TYF pair<ll, int> pli; _TYF pair<ll, ll> pll; _TYF pair<int, char> pic; _TYF pair<char, int> pci;
_TYF pair<char, char> pcc; _TYF pair<long, char> plc; _TYF pair<char, long> pcl; _TYF pair<ll, char> pllc; _TYF pair<char, ll> pcll;
_TYF pair<int, string> pis; _TYF pair<string, int> psi; _TYF pair<long, string> pls;
_TYF pair<string, long> psl; _TYF pair<ll, string> plls; _TYF pair<string, ll> psll;
_TYF pair<string, string> pss;
_TYF tuple<int, int, int> tiii; _TYF tuple<int, int, int, int> tiiii;
_TYF tuple<ll, ll, ll> tlll; _TYF tuple<ll, ll, ll, ll> tllll;
_TYF vector<string> vs; _TYF queue<string> qs; _TYF stack<string> ss; _TYF dq<string> dqs; _TYF pq<string> pqs; _TYF dq<string> dqs;
_TYF vector<char> vc; _TYF queue<char> qc; _TYF stack<char> sc; _TYF dq<char> dqc; _TYF pq<char> pqc; _TYF dq<char> dqc;
_TYF vector<int> vi; _TYF queue<int> qi; _TYF stack<int> si; _TYF dq<int> dqi; _TYF pq<int> pqi; _TYF dq<int> dqi;
_TYF vector<pii> vii; _TYF queue<pii> qii; _TYF stack<pii> sii; _TYF dq<pii> dqii; _TYF pq<pii> pqii; _TYF dq<pii> dqii;
_TYF vector<tiii> viii; _TYF queue<tiii> qiii; _TYF stack<tiii> siii; _TYF dq<tiii> dqiii; _TYF pq<tiii> pqiii; _TYF dq<tiii> dqiii;
_TYF vector<tiiii> viiii; _TYF queue<tiiii> qiiii; _TYF stack<tiiii> siiii; _TYF dq<tiiii> dqiiii; _TYF pq<tiiii> pqiiii; _TYF dq<tiiii> dqiiii;
_TYF vector<pll> vll; _TYF queue<pll> qll; _TYF stack<ll> sll; _TYF dq<pll> dqll; _TYF pq<pll> pqll; _TYF dq<pll> dqll;
_TYF vector<tlll> vlll; _TYF queue<tlll> qlll; _TYF stack<tlll> slll; _TYF dq<tlll> dqlll; _TYF pq<tlll> pqlll; _TYF dq<tlll> dqlll;
_TYF vector<tllll> vllll; _TYF queue<tllll> qllll; _TYF stack<tllll> sllll; _TYF dq<tllll> dqllll; _TYF pq<tllll> pqllll; _TYF dq<tllll> dqllll;
_TCE T sq(T num) { rt num* num; }//제곱함수
_TCE T GCD(T num1, T num2) { if (num2 == 0) rt num1; rt GCD(num2, num1 % num2); }
_TCE T LCM(T num1, T num2) { if (num1 == 0 || num2 == 0) rt num1 + num2; rt num1* (num2 / GCD(num1, num2)); }
//STL 전용 초기화 함수들 ( ms~~ )
_TCE void msq(T& a) { while (!a.empty()) a.PP(); }//queue clear
_TCE void msv(T& a) { a.cls(); }//vector clear
_TCE void msdq(T& a) { a.cls(); }//deque clear
_TCE void msm(T& a) { a.cls(); }//map clear
_TCE void mss(T& a) { while (!a.empty()) a.PP(); }//stack, set clear
_TCE void mspq(T& a) { while (!a.empty()) a.PP(); }//priority_queue clear
//pii operator - (pii a, pii b) { rt pii(a.first - b.first, a.second - b.second); }
//bool operator <= (pii a, pii b) { rt a.first <= b.first && a.second <= b.second; } 
//bool operator >= (pii a, pii b) { rt a.first >= b.first && a.second >= b.second; } 
//bool operator < (pii a, pii b) { if (a == b) return false; rt a <= b; } 
//bool operator > (pii a, pii b) { if (a == b) return false; rt a >= b; }

int N, mod = 1000000000, res;
int DP[100][10][1 << 10]; //비트필드를 이용한 DP, 자릿수, 현재숫자, 사용한숫자

//프로그램 메인 로직
void func() {
	sc("%d", &N);

	//9876543210 을 체크하기위한 비트모음.  (1 << 9 == 9, ..., 1 << 0 == 0)
	int full = (1 << 10) - 1;
	
	//N자릿수를 맨앞자릿수부터 탐색
	rep(idx, N) { //자릿수 idx 
		//맨첫자리는 0이 불가능한 초깃값으로 지정
		if (idx == 0) {
			rrep(num, 1, 10) //맨앞자리는 0제외 1~9만 가능
				DP[0][num][1 << num] = 1; //1가지 있음
			ct;
		}
		rep(num, 10) { //현재 자리에 사용된 숫자
			rep(bit, full + 1) { //0~9숫자가 체크됬는지 확인하기위한 비트셋
				
				//현재숫자를 기준으로 가능했던 이전 숫자들을 더해나감 (bottom-up)
				if (num == 0) //DP[idx][num][bit]에 여러번 값이 더해질 수 있다. 
							  //또한 문제는 나머지를 출력해야하니 기존값DP[idx][num][bit]에 더한뒤 바로 모드연산을 하여 저장한다.
					DP[idx][0][bit | (1 << 0)] = (DP[idx][0][bit | (1 << 0)] + DP[idx - 1][1][bit]) % mod;
				else if(1 <= num && num <= 8) {
					DP[idx][num][bit | 1 << num] = (DP[idx][num][bit | (1 << num)] + DP[idx - 1][num - 1][bit]) % mod;
					DP[idx][num][bit | 1 << num] = (DP[idx][num][bit | (1 << num)] + DP[idx - 1][num + 1][bit]) % mod;
				}
				else
					DP[idx][9][bit | (1 << 9)] = (DP[idx][9][bit | (1 << 9)] + DP[idx - 1][8][bit]) % mod;
			}
		}
	}

	//맨끝자리가 0~9일때의 각각의 DP값의 합을 출력
	//이때 모든 숫자를 사용한 full을 사용해 검색한다.
	//이또한 기존 res에 DP를 더한뒤 바로 mod연산해서 res에 더한다.
	rep(num, 10)
		res = (res + DP[N - 1][num][full]) % mod;

	pr("%d", res);
}


int main(void) {
	func();

	rt 0;
}