//약간 날림의 느낌이 있지만..

//음.. 틀린 것은 나중에 수정.. 일단 큰 맥락은 맞으니..

#include <stdio.h>

//N (1 <= N <= 12) : 전공 과목의 수

//K (0 <= K <= N) : 들어야 할 과목 수

//M (1 <= M <= 10) : 학기의 수

//L (1 <= L <= 10) : 한학기에 최대로 들을 수 있는 과목

//R (0 <= R <= N-1) : 선수과목의 수 => R 개의 선수과목 번호.

int n; // 전공 과목의 수

int k; // 들어야 하는 전공과목의 수

int m; // 학기의 수

int l; //한학기에 최대로 들을 수 있는 과목의 수

int pre_subject_no[12]; //각 번호마다 필요한 선수과목의 수

//int pre_subject[12][12]; //각 번호마다 필요한 선수과목

int pre_subject[12]={0,};

int cur_subject_no[12]; //각 학기 마다 열리는 과목 수

int cur_subject[12]; //각 학기 마다 열리는 과목

inline int bitCount(int hist){

    int ok=0;

    for(int i=0;i<n;i++){if(((hist >> i) & 1) ==1) ok++;}

    return ok;

}

int cache[1<<12][12];

//선수과목을 고려하여 n 개의 과목을 들을 수 있는 최소 학기 수를 돌려줌.

//taken : 들은 수업들, semester : 학기 수

int get_min_semester(int taken, int semester){

    //수업을 모두 들었을때.

    if(bitCount(taken)>=k) return 0;

    //학기가 m 을 넘어갔을때.

    if(semester==m) return 987654321;

                        //2147483647

    int &min = cache[taken][semester];

    if(min!=-1){return min;}

    min =987654321;

    //cut_subject 의 1~l 크기의 모든 부분집합을 순회 하며,

    //cur_subject[semester] 중 pre_subject[]를 만족하는 것만 추린다.

    // taken -> 들은 것

    //~taken -> 안들은 것

    int canTake=cur_subject[semester] & ~taken;//이번학기 개설 되는 것 중 아직 듣지 않은 것을 추린다.

    for(int i=0;i<cur_subject_no[semester];i++){

        if((canTake & 1<<i) && //아직 듣지 않은 과목 중

            (taken & pre_subject[i]) != pre_subject[i]){ //선수과목을 만족시키지 못하는 것을 추린다.

            //해당 과목만 지운다.

            canTake &= ~(1<<i);

        }

    }

    int temp;

    //canTake 를 순회

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

        if((i & canTake) ==i && bitCount(i) <=l){

            temp = get_min_semester(taken|i,semester + 1) + 1;

            min = min > temp ? temp : min;

        }

    }

\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0

    //이번 학기에 수업을 하나도 듣지 않는 경우는 semester 수에서 제외한다. 그래서 +1 이 없다.

    temp = get_min_semester(taken,semester + 1);

    min = min > temp ? temp : min;

    return min;

}

int main(){

    for(int i=0;i<(1<<12);i++){

        for(int j=0;j<12;j++){

        cache[i][j]=-1;

        }

    }

    int ret;

    n = 4;    k = 4;    m = 4;    l = 4;

    //해당 과목의 선수 과목 수

    pre_subject_no[0]=0;

    pre_subject_no[1]=1;

    pre_subject_no[2]=3;

    pre_subject_no[3]=0;

    //해당 과목의 선수 과목

    pre_subject[1]|=1<<0; //0

    pre_subject[2]|=1<<0; //0

    pre_subject[2]|=1<<1; //1

    pre_subject[2]|=1<<3; //3

    //이번 학기 부터 순서대로 각 학기의 정보

    //m개의 학기 마다 수업 정보

    cur_subject_no[0]=4;

    cur_subject_no[1]=4;

    cur_subject_no[2]=3;

    cur_subject_no[3]=4;

    //해당 과목의 번호

    cur_subject[0] |= 1; //0

 &nbs\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0p;  cur_subject[0] |= 1<<1; //1

    cur_subject[0] |= 1<<2; //2

    cur_subject[0] |= 1<<3; //3

    cur_subject[1] |= 1;

    cur_subject[1] |= 1<<1;

    cur_subject[1] |= 1<<2;

    cur_subject[1] |= 1<<3;

    cur_subject[2] |= 1;

    cur_subject[2] |= 1<<1;

    cur_subject[2] |= 1<<3;

    cur_subject[3] |= 1;

    cur_subject[3] |= 1<<1;

    cur_subject[3] |= 1<<2;

    cur_subject[3] |= 1<<3;

    //k개의 과목을 마칠 수 있는 최소 학기 수를 돌려준다.

    ret = get_min_semester(0,0);

    if(ret == 987654321){

        printf("IMPOSSIBLE

");

    }else{

        printf("%d

",ret);

    }

}

제한 조건이 있는 경우 제한 조건까지 충족하며 memoization 을

할 수 없는 경우, 제한 조건 없는 것에서 제한 조건 있는 경우를

빼는 방법도 있음.

#define MOD 1000000007

int arr[100];

int cache[101];

int tile(int remain){

    if(remain <= 1)    return 1;

    int &ret = cache[remain];

    if(ret != 0){return ret;}

    ret = (tile(remain-1)%MOD) + (tile(remain-2)%MOD);

    ret = ret % MOD;

    return ret;

}

int atile(int remain){

    //홀수라면

    if(remain %2 ==1){

        return (tile(remain) - tile(remain/2) + MOD)%MOD;

    }

    //짝수 라면

    int ret = tile(remain);

    ret = (ret - tile(remain/2) + MOD)%MOD;//가운데가 없는 것도 빼고

    ret = (ret - tile(remain/2-1) + MOD)%MOD;//가운데가 누워 있는 것도 빼고.

return ret;

}

int main(){

    //printf("The Number is %d

",tile(2));

    for(int i=0;i<101;i++){

            cache[i] = 0;

    }

    printf("The Number is %d

",atile(2));

    for(int i=0;i<101;i++){

            cache[i] = 0;

    }

    printf("The Number is %d

",atile(4));

    for(int i=0;i<101;i++){

            cache[i] = 0;

    }

    printf("The Number is %d

",atile(5));

    for(int i=0;i<101;i++){

            cache[i] = 0;

    }

    printf("The Number is %d

",atile(92));

    return 0;

}

뭔가 하지 않을 때는

이 사이트에 아무것도 남기지 않는구나^^;;

inline int mymin(int a, int b){ return a<b?a:b;}

inline int mymax(int a, int b){ return a>b?a:b;}

int fence[20000];

int cache[20000][20000];

int solve(int left, int right){

    if(left==right){return fence[left];}

    int mid = (left + right)/2;

    int &ret = cache[left][right];

    if(ret != 0){return ret;}

    ret = mymax(solve(left,mid),solve(mid+1,right));

    int l = mid;

    int r = mid+1;

    int height = mymin(fence[l],fence[r]);

    ret = mymax(height*2,ret);

    //ㅣ 이 아직 left보다 크거나 r 이 right 보다 작은 동안 계속 돈다.

    //height 는 가운데 두 개 판자중 낮은 것의 높이부터 시작.

    while(left < l || r < right){

        // r 이 right 보다 작고, l이 이미 left에이미 도달 해서 더 갈 수 없거나 오른쪽 fence 가 더 높을때 오른쪽 으로 간다.

        if(r < right && (l==left || fence[l-1] < fence[r+1])){

            r++;

            height = mymin(fence[r],height);

        }else{

            l++;

            height = mymin(fence[l],height);

        }

        //ret와 지금 가진 좌우 * 높이 중 더 큰것을 취한다.

        ret = mymax(ret, height * ( r - l +1 ));

    }

    return ret;

}