const int MAX = 1000000000 + 1;
int length[51];
void precalc() {
length[0] = 1;
for(int i = 1 ; i < 51 ; i++) {
length[i] = min(MAX, 2 + 2 * length[i-1]);
}
}
const string EXPAND_X = "X+YF";
const string EXPAND_Y = "FX-Y";
char expand(const string& dragoon, int generation, int skip) {
// 기저 사례
if(generation == 0) {
return dragoon[skip];
}
for(int i = 0 ; i < dragoon.size() ; ++i) {
if(dragoon[i] == 'X' || dragoon[i] == 'Y') {
if(skip > length[generation])
skip -= length[generation];
else if(dragoon[i] == 'X')
return expand(EXPAND_X, generation - 1, skip);
else
return expand(EXPAND_Y, generation - 1, skip);
else if(skip > 0) // 확장되지는 않지만 한칸 건너 뛰어야 하는 경우 (F,+,-)
--skip;
else // 답을 찾은 경우
return dragoon[i];
}
}
return "#";
}
#include <stdio.h>
#include <stdlib.h>
const int MOD = 10*1000*1000;
int cache[101][101];
int N = 12;
int count = 0; // 메모이제이션 적용 시, 성능을 확인하기 위한 cnt
// - poly(int n, int first)함수의 기능 -
// -> n개의 정사각형으로 이루어졌고, 맨 위 가로줄에 first개의
// 정사각형을 포함하는 폴리오미노의 수를 반환함
int poly(int n, int first){
if(n == first) return 1;
int& ret = cache[n][first];
if (ret != -1) return ret;
ret = 0;
for(int second = 1 ; second <= n-first ; ++second){
int add = second + first -1;
int sum = poly(n-first, second);
count++;
// DSP 메모이제이션 상태 저장
int temp = n - first;
cache[temp][second] = sum;
add = add * sum;
add %= MOD;
ret += add;
ret %= MOD;
}
return ret;
}
int main()
{
for(int i = 0 ; i < 101 ; i++)
for(int j = 0 ; j < 101 ; j++)
cache[i][j] = -1;
int ret = 0;
for(int i = 1 ; i <= N ; i++)
{
ret += poly(N, i);
ret %= MOD;
}
printf("%d, cnt : %d", ret, count);
system("pause");
return 0;
}
#define MAX_QUEUE_SIZE 6
static char queue[MAX_QUEUE_SIZE];
int main(void)
{
int front, rear;
front = rear = 0;
int ret;
addQeueu(&rear, front, 'A');
addQeueu(&rear, front, 'B');
addQeueu(&rear, front, 'C');
ret = delQueue(&front, rear);
system("pause");
return 0;
}
void addQeueu(int last, int first, int data)
{
*last = (*last + 1) % MAX_QUEUE_SIZE;
if(*last == first) {
queue_full(); // 구현은 생략 : last 즉 rear이 이동 되었기 때문에 reset 작업 필요
return;
}
queue[*last] = data;
}
int delQueue(int first, int last)
{
if(*first == last) {
return queue_empty(); // 구현은 생략
}
*first = (*first + 1) % MAX_QUEUE_SIZE;
return queue[*first];
}
Prev
Rss Feed