백준 1562 c++ "계단 수" -PlusUltraCode-

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

 

[필자 사고]

 

어려운 문제다.

처음에 DNS를 이용하여 풀려고 했지만 경우의 수를 생각해보니 시간초과가 나온다.

어쩔 수 없이 30분 고민하고 풀이 힌트를 보았더니 비트마스킹을 이용한 동적프로그래밍 문제다.

 

나는 처음으로 비트마스킹 알고리즘을 만나게 되었따.

 

간단히 말하자면

1000000000 이라는 2진수로 이루어진 bit가 있고

1<<5 라고 하면 10000 식으로 

위의 기존 bit | new bit 를 하게 되면

1000010000 식으로 게임 처럼 1로 바껴서 on모드가 된다.

이러한 방식으로 아래의 문제를 해결했다. 

 

 

소스코드 해설은 아래와 같다

 

1.코드 개요
이 코드는 숫자의 길이 N이 주어졌을 때, 계단 수를 계산하는 프로그램입니다. 계단 수는 숫자의 각 자릿수가 1씩 증가하거나 감소하는 수를 의미하며, 이 코드에서는 모든 0부터 9까지의 숫자를 한 번씩 포함하는 계단 수의 개수를 구합니다. 동적 프로그래밍(DP)과 비트마스킹을 사용하여 문제를 해결합니다.

2. 입력과 초기화
입력으로 숫자의 길이 N을 받고, DP 배열을 초기화합니다. DP 배열은 계산 결과를 저장하여 중복 계산을 방지하며, 아직 계산되지 않은 상태를 나타내기 위해 -1로 초기화됩니다.

 

3.계단 수 계산 (재귀 함수)
sol 함수는 재귀적으로 호출되며, 현재 상태를 기반으로 가능한 모든 계단 수를 탐색합니다.

• 기저 조건
  숫자의 길이가 N에 도달했을 때, 현재까지 사용한 숫자가 0부터 9까지 모두 포함되었는지를 확인합니다. 모든 숫자가 포함되었다면 1을 반환하고, 그렇지 않다면 0을 반환합니다.
• 메모이제이션
  이미 계산된 경우, 저장된 결과를 반환하여 불필요한 계산을 방지합니다.
• 현재 숫자 사용 기록
  현재 자릿수를 비트마스킹으로 기록합니다. 이를 통해 어떤 숫자가 사용되었는지 추적할 수 있습니다.
• 재귀 호출
  계단 수의 조건에 따라, 현재 숫자에서 1 증가하거나 1 감소한 숫자로 이동하며 다음 자릿수를 탐색합니다.

4. 최종 결과 계산
숫자의 길이가 1인 경우부터 시작해 각 숫자를 초기값으로 설정하고, 가능한 모든 경로를 탐색하여 결과를 누적합니다. 최종적으로 구한 계단 수의 개수를 출력합니다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>

using namespace std;

int N, dp[101][10][1 << 10], mod = 1e9;
int sol(int n, int m, int bit) {
	if (n == N) return ((1 << m) | bit) == ((1 << 10) - 1);

	int& ret = dp[n][m][bit];
	if (ret != -1) return ret;
	ret = 0;
	bit |= (1 << m);
	if (m - 1 >= 0) ret = (ret + sol(n + 1, m - 1, bit)) % mod;
	if (m + 1 < 10) ret = (ret + sol(n + 1, m + 1, bit)) % mod;
	return ret;
}

int main(void) {
	scanf("%d", &N);
	memset(dp, -1, sizeof(dp));
	int ans = 0;
	for (int i = 1; i < 10; i++) {
		ans += sol(1, i, 0);
		ans %= mod;
	}
	printf("%d", ans);
}