boj, 백준) 1562. 계단 수( C / C++)

1. 문제 링크

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

1562번: 계단 수

2. 문제 개요

계단수는 인접한 모든 자릿수의 차이가 1이 난다. 

0부터 9까지 모든 한 자릿수가 자릿수로 등장하면서, 수의 길이가 N인 계단 수가 몇 개 있는지 찾아보자.

3. 문제 힌트

   dp[n][i]라 두고, n을 자릿수, i를 가장 오른쪽의 수라고 가정했을 때는 0~9까지 모두 사용하지 않은 계단 수를 구할 수 있다.

그럼, 0~9까지 다 사용했음을 어떻게 표현하면 좋을까? 상태를 추가하면 좋을것같은데!!

 

 

4. 문제 풀이

상태를 추가해보자.

(1) dp[n][i][x][y] 처음에 접근한 방식이었다. 이때까지 사용한 수의 최솟값 x 최댓값 y라고 정의하고 dp[n][0~9][0][9]를 구하면 된다.

 

(2) dp[n][i][1024]로 정의하여 1번이라도 사용한 수의 bit를 1로 올려주는 방법

 

(3) dp[n][i][1][1][1][1][....][1][1] 이거는 풀고 나서 다른 사람의 풀이를 봤는데 있었다.

 

(4) 4개의 상태로 풀 수도 있다고 하는데 읽어보지는 않았다.

 

여기서는 2번을 풀이에 사용할 것이다.

처음에 1번으로 풀이를 했었는데 뭔가 dp가 꼬여서 어려웠다.

예를 들면 3이라는 상태에서 4를 추가할 때 상태는 7이 된다. 그런데, 7이라는 상태에서 4를 추가해도 7이 된다. 즉 여러 개가 도달할 수 있기 때문에 (1) 번과 같은 디자인으로는 빠른 시간에 코드가 떠오르지 않았다.

 

그래서 풀다가 (2) 번의 방식으로 변경했는데

next state는 cur state에서 마지막에 추가할 number를 or 해주면 된다.

그러면 (1) 번 유형으로 풀었을 때의 걱정을 없앨 수 있다.

number가 0인 경우에는

즉, dp[i][number][cur state | (1 << number)] += dp[i-1][number + 1][cur state]가 될 것이다.

여기서 +=를 해준 이유는 위처럼 7의 상태 (00 0000 0111)에서 4가 들어와도 7, 3의 상태에서 4가 들어와도 7처럼 중복되는 경우가 있기 때문에 기존의 값에 누적시켜주는 형태로 해야 한다.

 

'<<'연산은 왼쪽으로 number 수만큼 이동시키는 연산이다.

만약 마지막 자리에 3이 추가되었다면, 00 0000 1000이 추가되어야 하고 이것은 or연산으로 나타낼 수 있다.

 

그래서 구하고자 하는 값은 n번째 자리이고, 모든 숫자가 사용되었으며(1023 = 11 1111 1111), 마지막 자리가 0~9인 수.

 

즉

ans += dp[n][0~9][1023]이 될 것이다.

mod = 1,000,000,000을 적용하는 것을 까먹지 말자.

mod를 깜빡해서 2번이나 틀렸다. 

0이 9개인데 8개 적고 왜 틀렸지...

맞 왜 틀

 

그냥 모조리 mod를 다 추가시켰다.

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
 
int n;
int dp[101][10][1024];	
 
const int mod = 1000000000;
 
int main()
{
	scanf("%d", &n);
 
	//base
	dp[1][0][1] = 0;	//명시적
	dp[1][1][2] = 1;
	dp[1][2][4] = 1;
	dp[1][3][8] = 1;
	dp[1][4][16] = 1;
	dp[1][5][32] = 1;
	dp[1][6][64] = 1;
	dp[1][7][128] = 1;
	dp[1][8][256] = 1;
	dp[1][9][512] = 1;
 
	//step
	for (int i = 2; i <= n; ++i) {
		for (int cur = 0; cur <= 9; ++cur) {
			for (int state = 0; state <= 1023; ++state) {
				if (cur == 0) {
						dp[i][cur][state | (1 << cur)] = (dp[i][cur][state | (1 << cur)] + dp[i - 1][cur + 1][state])%mod;
				}
				else if (cur == 9) {
					dp[i][cur][state | (1 << cur)] = (dp[i][cur][state | (1 << cur)] + dp[i - 1][cur - 1][state]) % mod;
				}
				else{
					dp[i][cur][state | (1 << cur)] = (dp[i][cur][state | (1 << cur)] + dp[i - 1][cur + 1][state]) % mod;
					dp[i][cur][state | (1 << cur)] = (dp[i][cur][state | (1 << cur)] + dp[i - 1][cur - 1][state]) % mod;
				}
			}
		}
	}
 
	int ans = 0;
	for (int cur = 0; cur <= 9; ++cur)
		ans = (ans + dp[n][cur][1023]) % mod;
	printf("%d", ans);
	return 0;
}

6. 결과 사진

 

지적, 댓글 언제나 환영입니다~