[백준][C++]1562 - 계단 수

문제

• 1562번 : 계단 수
• Rank : Gold I
• 링크 : https://www.acmicpc.net/problem/1562

1562번: 계단 수

풀이 전략

• 모든 경우의 수를 구하는 문제
• 현재 수를 구할 필요는 없다(0~9까지의 숫자가 모두 등장하는지만을 확인하면 된다)
  • 비트마스킹으로 모든 수가 등장하는지를 확인한다.
• 0~8에서는 다음 수로, 1~9에서는 이전 수로 이동할 수 있다(9->0, 0->9는 불가능하다)
• 남은 인덱스, 현재 숫자, 비스마스크된 숫자를 함수 인자로 활용한다.
• unsigned long run(int lastDigit, int idx, unsigned int cBitMask)
• N의 값이 높을 경우 중복되는 함수 호출이 많아 속도를 확보하지 못하므로, 배열을 사용하여 메모이제이션해준다.
  • 답의 범위는 (0 ~ 999999999) * 2이므로, unsigned long으로 처리 가능하다.
    • *2 하는 이유는 경우의수를 구하는 과정에서 두 run의 값을 더하기 떄문이다.
  • bistmask : 0~1023, idx : 0~100, lastDigit : 0~9 이므로 1024*101*10 = 약 백만개의 변수를 사용한다.
    • 문제의 메모리 제한이 128MB이므로, 충분히 사용 가능하다.
  • 남은 숫자(idx)가 0이고, Digit이 모두 찬 경우(1023)는 경우의 수가 1이므로, 1로 선언하여둔다.
  • idx가 0인 나머지경우는 조건을 만족하지 못했으므로 0으로 처리하고, 남은 경우는 계산하여 저장한다.

전체 소스 코드

//Backjoon Problem No.1562
//https://www.acmicpc.net/problem/1562
//Mist16, 2022-03-08

#include <iostream>

using namespace std;

unsigned int answerBitmask = 0b1111111111;

unsigned long answerBoard[1024][101][10] = { 0, };

void initialize()
{
	for (int i = 0; i <= 9; i++)
	{
		answerBoard[answerBitmask][0][i] = 1;
	}
}


unsigned long run(int lastDigit, int idx, unsigned int cBitMask)
{
	unsigned long answer = 0;
	if (answerBoard[cBitMask][idx][lastDigit] != 0)
		return answerBoard[cBitMask][idx][lastDigit];
	if (idx == 0)
		return 0;
	//+1
	if (lastDigit < 9)
	{
		answer += run(lastDigit + 1, idx - 1, cBitMask | (1 << (lastDigit + 1)));
	}
	//-1
	if (lastDigit > 0)
	{
		answer += run(lastDigit - 1, idx - 1, cBitMask | (1 << (lastDigit - 1)));
	}	
	answer = answer % 1000000000;
	answerBoard[cBitMask][idx][lastDigit] = answer;
	return answer;
}

int main()
{
	unsigned long long tAnswer = 0;
	unsigned long answer = 0;
	int N;
	cin >> N;

	initialize();

	for (int i = 1; i <= 9; i++)
	{
		answer += run(i, N - 1, (1 << i));
		answer = answer % 1000000000;
	}
	cout << answer;
	return 0;
}

Note

• 생각보다 큰 사이즈의 배열이라도 메모이제이션을 써야 할 경우가 있다.
  • 경우의 수는 크지만 실제 도출되는 계산의 양이 적은 경우는, STL map등을 사용하여 메모리를 절약할 수 있다.