[BOJ] 1562 계단 수

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

1562번: 계단 수

문제

45656이란 수를 보자.

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

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

입력

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

10

출력

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

1

---

오랜만에 DP 문제를 푼 것 같다.

몇번 지나친 적이 있는 문제였다.

이런 식의 문제는 보통 수학 개념이 들어가길래 그냥 지나쳤었는데 막상 풀고보니 쌩DP 문제였다.

 

점화식 자체는 금방 떠올렸지만 0~9가 모두 들어가도록 코드를 짜는게 쉽지 않았다.

이 부분은 다른 사람들의 코드를 보고 힌트를 얻어서 해결했다.

 

저번에 풀었던 문제랑 비슷하게 비트마스킹을 활용하는 부분이 있었다.

그 문제를 풀면서 비트를 다루는 것이 그리 어색하지 않다고 했었는데

비트를 다루는 것 자체는 익숙하지만 이런 식의 접근을 떠올리는게 어려웠다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

#define MOD 1000000000

int N;
int dp[101][10][1<<10];

int main() {
	scanf("%d", &N);
    
	for (int i = 1; i <= 9; i++)
		dp[1][i][1 << i] = 1;

	for (int i = 2; i <= N; i++) {
		for (int j = 0; j <= 9; j++) {
			for (int k = 0; k < 1024; k++) {
				if (j == 0)
					dp[i][0][k | (1 << 0)] = 
                    (dp[i][0][k | (1 << 0)] + dp[i - 1][1][k]) % MOD;
				else if (j == 9)
					dp[i][9][k | (1 << 9)] = 
                    (dp[i][9][k | (1 << 9)] + dp[i - 1][8][k]) % MOD;
				else {
					dp[i][j][k | (1 << j)] = 
                    (dp[i][j][k | (1 << j)] + dp[i - 1][j - 1][k]) % MOD;
					dp[i][j][k | (1 << j)] = 
                    (dp[i][j][k | (1 << j)] + dp[i - 1][j + 1][k]) % MOD;
				}
			}
		}
	}

	int answer = 0;

	for (int i = 0; i <= 9; i++)
		answer = (answer + dp[N][i][1023]) % MOD;

	printf("%d", answer );

	return 0;
}

 

후기)

DP를 푸는 경우에 예전보다는 쉽게 점화식을 알아내지만 그걸 구현하는 실력이 아직 부족한 것 같다. 

 

코드가 예쁘게 올라가지지 않는다... 너무 불편하다....

아직 블로그를 많이 해보지 않아서 어떤 식으로 올려야 잘 올라가는지를 모르겠다.