[1562] 계단수

[문제]

45656이란 수를 보자.

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

그럼, 오늘도 역시 세준이는 0부터 9까지 모든 한 자리수가 자리수로 등장하면서, 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N이면서 0에서 9가 모두 등장하는 계단 수가 총 몇 개 있는 지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

[풀이]

필요한 입력데이터를 간추려 보면 현재 자릿수, 값, 그리고 각 자리수를 한번이라도 넣었는지 확인하는 변수가 필요합니다.

chairCount(location, value, state)는 해석하면 현재 자릿수에서 해당 값을 넣었을 때의 경우의 수에 대한 정보를 가지고 있습니다. 

주의 깊게 봐야할 점은 2가지가 있습니다.

1. long long 타입을 사용. 경우의 수가 상당히 크기 때문에 long long 타입을 사용하였고 출력서식형태는 %lld 입니다.

2. state는 해당 값을 이전에 넣었다면 true/false로 관리하기 위해 배열을 사용할 수 있지만 아래와 같이 비트마스크를 이용하여 관리할 수 있습니다. (state | 1<<value) 로 하여 value 자리에 1을 채워넣을 수 있습니다.

#include <stdio.h>

#include <string.h>

#define MOD 1000000000

int n;

long long cache[101][11][1<<11];

int chairCount(int location, int value, int state) {

if(value<0 || value>9) return 0;

if(location == n) {

if((state | (1<<value)) == (1<<10)-1) return 1;

else return 0;

}

long long & ret = cache[location][value][state];

if(ret!=-1) return ret;

state |= (1<<value);

return ret = (chairCount(location+1, value+1, state) + chairCount(location+1, value-1, state) ) % MOD;

}

int  main() {

scanf("%d", &n);

memset(cache, -1, sizeof(cache));

long long count = 0;

for(int i=1 ; i<=9 ; i++) {

count = (count + chairCount(1, i, 0)) % MOD;

}

printf("%lld", count);

return 0;

}