[BOJ] 1562번 : 계단 수(C++)[Gold I]

김준형·2021년 5월 2일
1

백준

목록 보기
8/13
post-thumbnail

문제 풀러가기

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}; // +1, -1의 계산을 for문으로 하기 위한 배열
LL cache[11][101][(1<<10)+1]; // memoization
// DFS함수
// start : 현재 number(0~9)
// idx : 현재 number의 위치(0~99)
// state : 0~9의 상태를 나타내기 위한 수
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 retreturn ret %= INF로 바꿔 문제를 해결하였다.
profile
코딩하는 군인입니다.

0개의 댓글