문제 풀러가기
Problem
Solution
- 조건
0에서 9가 모두 등장하는
을 무시하고 길이가 N인 계단 수를 먼저 고려해보았다.
- DFS함수에 Memoization을 적용, 2차원 배열
cache[start][idx]
을 이용하여
문제를 해결할 수 있다.
- 조건
0에서 9가 모두 등장하는
을 고려해보자. 현재 0에서 9중 어떤 숫자들이 등장하였는지를
나타내는 상태가 필요하다. 이는 BitMask기법을 통해 간단하게 해결할 수 있다.
- 위의 2차원 배열에 상태를 나타내는 state변수를 추가한 3차원 배열
cache[start][idx][state]
을 이용하여 문제를 해결한다.
- N=1일때부터, N=40일 때 까지 답을 모두 더하면 int형 정수로 표현할 수 없는 수가 나오므로
long long형을 사용한다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#define MAX 1023
#define LL long long
const LL INF = 1e9;
using namespace std;
int N;
int dx[2] = {+1, -1};
LL cache[11][101][(1<<10)+1];
LL solve(int start, int idx, int state){
if(idx == N-1){
if(state == MAX) return 1;
else return 0;
}
LL& ret = cache[start][idx][state];
if(ret != -1) return ret;
ret = 0;
for(int i=0; i<2; i++){
int next = start + dx[i];
if(next == 10 || next == -1) continue;
ret += solve(next, idx + 1, state | 1<<next);
}
return ret %= INF;
}
int main(){
scanf("%d", &N);
memset(cache, -1, sizeof(cache));
LL ans = 0;
for(int i=1; i<10; i++)
ans += solve(i, 0, 1<<i);
printf("%lld \n", ans % INF);
}
Result
- 코드를 실행했을 때 N=1일때부터, N=40일 때 까지 답을 모두 더해서 126461847755이 나왔다.
하지만 틀렸다는 메세지가 나왔고 cache의 크기를 잘못 설정한 것으로 판단하여 크기를 조절해봤다.
- N = 90일 때 (-)값이 나오는 것을 확인하였고 long long 형으로도 값을 온전히 저장할 수 없다는 것을 파악하였다. solve함수의
return ret
을 return ret %= INF
로 바꿔 문제를 해결하였다.