계단 수(DP)

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

10844번: 쉬운 계단 수

 

쉬운 계단 수 문제를 먼저 보자.

 

길이가 N인 계단 수에서 맨 끝에 숫자를 추가하면 길이가 N+1인 계단 수가 된다.

이때 더할 수 있는 숫자는 기존의 계단 수의 가장 끝의 숫자로 판단한다.

0, 9일때는 각각 1과 8이고 1~8의 숫자는 각각 2가지의 숫자가 될 것이다.

DP[i][j] i = 계단 수의 길이 j = 가장 끝의 숫자 저장하는 값 = i길이의 수열에서 끝의 숫자가 j일때 해당 수열로 특정 길이의 계단 수를 만들 수 있는 갯수

 

이런 방법을 재귀함수와 메모이제이션으로 구현하고 길이가 충족할때 1을 리턴해주면 된다.

DP[i][j] = DP[i+1][j+1] + DP[i+1][j-1] ※ 해당 점화식 자체로 계단 수의 조건을 충족하게 됨 ※ j가 0일때는 DP[i+1][j+1] 값만, 9일때는 DP[i+1][j-1] 값만 ※ i == 계단 수의 길이일때는 DP[i][j] = 1

 

DP[i][j]를 j로 끝나는 i길이의 계단 수의 갯수로 정의하고

DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1], i = 1일때 DP[i][j] = 1로 접근하는 방법이 더 직관적이지만

하단의 어려운 계단 수 문제와의 연결을 위해 다른 방향으로 접근하였다.

 

재귀함수 호출 후 DP[1][1~9]를 전부 더해주면 된다.

#include <iostream>
using namespace std;

int DP[101][10] = { 0, };
int n;

int Solve(int size, int num)
{
	if (DP[size][num] != 0) return DP[size][num];
	if (size == n) return 1;

	if (num == 0)
	{
		DP[size][num] = Solve(size + 1, num + 1);
	}
	else if (num == 9)
	{
		DP[size][num] = Solve(size + 1, num - 1);
	}
	else
	{
		DP[size][num] =
			Solve(size + 1, num - 1) +
			Solve(size + 1, num + 1);
	}
	DP[size][num] %= 1000000000;
	return DP[size][num];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	int ret = 0;
	for (int i = 1; i < 10; i++)
	{
		ret += Solve(1, i);
		ret %= 1000000000;
	}
	cout << ret;
}

 

---

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

1562번: 계단 수

 

쉬운 계단 수 문제에서 0부터 9까지의 모든 숫자가 등장해야하는 조건이 추가되었다.

 

쉬운 계단 수 문제에서 재귀함수가 1을 리턴하는 조건이 계단 수의 길이 하나였다면

이번 계단 수 문제에선 길이와 모든 숫자가 등장했는지 여부까지 1을 리턴하는 조건에 포함되게 된다.

숫자의 등장 여부는 10비트 값에 해당하는 인덱스를 사용하는 것이 효율적이다.

DP[i][j][k] i = 계단 수의 길이 j = 가장 끝의 숫자 k = 숫자가 등장했는지 체크하는 10비트 배열(1 << 10) 저장하는 값 = i길이의 수열에서 끝의 숫자가 j이고 숫자가 k처럼 사용되었을때 해당 수열로 조건을 만족하는(길이, 0~9까지 전부 사용됨) 계단 수를 만들 수 있는 갯수

 

숫자를 추가하는 과정에서 비트 마스킹 기법으로 해당 숫자가 등장했다는 표시를 해줘야한다.

DP[i][j][k] = DP[i+1][j+1][k | (1 << j+1)] + DP[i+1][j-1][k | (1 << j-1)] ※ j가 0일때는 DP[i+1][j+1][k | (1 << j+1)] 값만, j가 9일때는 DP[i+1][j-1][k | (1 << j-1)] 값만 ※ i == 계단 수의 길이 && k == 1 << 10 - 1일때는 DP[i][j][k] = 1

 

재귀함수 호출 후 DP[1][1~9][1 << 1~9]의 값을 전부 더해주면 된다.

#include <iostream>
using namespace std;

int DP[101][10][1 << 10] = { 0, };
int n;

int Solve(int size, int num, int bit)
{
	if (DP[size][num][bit] != 0) return DP[size][num][bit];
	if (size == n) return bit == (1 << 10) - 1 ? 1 : 0;

	if (num == 0)
	{
		DP[size][num][bit] = Solve(size + 1, num + 1, bit | (1 << (num + 1)));
	}
	else if (num == 9)
	{
		DP[size][num][bit] = Solve(size + 1, num - 1, bit | (1 << (num - 1)));
	}
	else
	{
		DP[size][num][bit] = 
			Solve(size + 1, num - 1, bit | (1 << (num - 1))) +
			Solve(size + 1, num + 1, bit | (1 << (num + 1)));
	}
	DP[size][num][bit] %= 1000000000;
	return DP[size][num][bit];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	int ret = 0;
	for (int i = 1; i < 10; i++)
	{
		ret += Solve(1, i, 1 << i);
		ret %= 1000000000;
	}
	cout << ret;
}