[BOJ][C++] 1562번 계단 수

안녕하세요.

오늘은 백준 1562번: 계단 수(링크)  문제를 풀어보려고 합니다.

 

문제

45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다.

 

입력

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

 

출력

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

 

예제 입력

10

 

예제 출력

1

 

제한

시간 제한: 2초

메모리 제한: 128MB

 

---

풀이

먼저 쉬운 계단 수를 풀고 오면 이해가 더 쉽다.

 

쉬운 계단 수에서 정의한 DP에 따르면 아래와 같은 점화식이 만들어진다.

 

 

그러나 이번 문제는 0부터 9까지 숫자가 모두 등장했는지 확인해야 한다.

즉, 현재까지 등장한(방문한) 숫자를 체크하는 공간이 필요하다.

 

이때 사용하는 것이 비트필트(비트마스크) DP 방법이다.

아래 글을 참고해서 문제를 풀어보았다.

https://velog.io/@js43o/%EB%B0%B1%EC%A4%80-1562%EB%B2%88-%EA%B3%84%EB%8B%A8-%EC%88%98

[백준] 1562번: 계단 수

 

일단 현재까지 방문한 진행상황을 기록하기 위해 dp를 기존 2차원에서 3차원으로 만들어야 한다.

그 후 방문하는 것을 기록할 때, 비트마스크 기법을 사용해서 진행한다.

즉, 0000000000이면 아무것도 방문을 안한 것이고 0000000100이면 숫자 2 하나를 방문했다는 의미가 된다.

이진수로 0000000000~1111111111은 십진수로 나타내면 0~1023까지이므로 dp배열을 아래와 같이 만든다.

 

 

이를 통해 아래와 같이 진행할 수 있다.

 

만약 어떤 k번째 수를 탐색한다고 한다면, 이때의 bit는 bit | 1 << k가 될 것이다.

그때의 bit를 newBit라고 정의한다면, 다음과 같이 점화식을 세울 수 있다.

 

해당 점화식을 토대로 코드를 작성해나가면 된다.

정답

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
using ll = long long;
int n;
ll m = 1000000000;
int dp[101][10][1024];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin.tie(NULL);
	cin >> n;
	// 기존
	//dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
	// 비트마스크를 쓰는 이유
	// -> 현재(n)까지 방문한(처리한) 경우를 저장해서 사용하기 위함.

	for (int k = 1; k <= 9; k++) {
		dp[1][k][1 << k] = 1; // 1~9까지의 숫자는 방문한 숫자가 각각 자기 자신임(1<<k)
	}

	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			for (int bit = 0; bit < 1 << 10; bit++) {
				// bit | (1 << j) -> 이전까지 방문한 기록에 현재 숫자 j 방문했다고 기록함
				//dp[i][j][] = dp[]
				int newBit = bit | (1 << j);
				if (j < 9) dp[i][j][newBit] += dp[i - 1][j + 1][bit];
				if (j > 0) dp[i][j][newBit] += dp[i - 1][j - 1][bit];
				dp[i][j][newBit] %= m;
			}
		}
	}
	//dp[n][m][1<<k]: 길이가 n인 숫자에서 끝자리가 m이고 현재까지 방문한 숫자 집합이 1<<k인 경우의 수
	ll sum = 0;
	for (int j = 0; j <= 9; j++) {
		sum += dp[n][j][1023];
		sum %= m;
	}
	cout << sum;
}

---

이렇게 해서 백준 1562번 계단 수 문제를 풀어보았습니다.

 

댓글로 질문을 남기시면 성실히 답해드리겠습니다

 

감사합니다!

 

참고

https://velog.io/@js43o/%EB%B0%B1%EC%A4%80-1562%EB%B2%88-%EA%B3%84%EB%8B%A8-%EC%88%98

[백준] 1562번: 계단 수

 

https://sfer7.tistory.com/46

[백준] 1562번 : 계단 수 - C++ / JAVA