fork download 
  1. // 본 문제를 피보나치 수열로 풀었습니다.
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5.  
  6. int A[120][51];       // 만들수 잇는 블록의 경우를 더해감
  7. int common[120][51];  // 대칭되는 블록의 경우를 계산
  8. int sol[120][51];  // 만들수있는 경우와 대칭되는 경우를 뺌.
  9. int in[60];    // 입력으로 받는 타일 n을 받는 배열
  10. long long  sum;  // 문자열로 나눗셈을 하기위해 쓴 변수
  11.  
  12. int main()
  13. {
  14. int C,i,j,s,max,t;  //C는 받아들이는 경우의 수 C
  15.  
  16.  
  17.     scanf("%d",&C);
  18.  
  19.     for(i=1;i<=C;i++)scanf("%d",&in[i]);
  20.  
  21. common[1][50] = 1;
  22. common[1][0] = 1;
  23. common[2][50] = 2;
  24. common[2][0] = 1;
  25. common[3][50] = 1;
  26. common[3][0] = 1;
  27. common[4][50] = 3;
  28. common[4][0] = 1;
  29.  
  30. A[1][50] = 1;
  31. A[2][50] = 2;
  32. A[1][0] = 1;
  33. A[2][0] = 1;
  34.  
  35. for(i=1;i<=50;i++)  //좌우대칭타일 홀수부의 피보나치 수열
  36. {
  37.     if(common[2*i+1][0]>common[2*i-1][0])
  38.     s = common[2*i+1][0];
  39.     else s = common[2*i-1][0];
  40.     for(j=50;50-s<j;j--)
  41.     {
  42.         common[2*i+3][j] =common[2*i+3][j]+common[2*i+1][j] + common[2*i-1][j];
  43.         if(common[2*i+3][j]>=10)
  44.         {
  45.             common[2*i+3][j]= common[2*i+3][j]-10;
  46.             common[2*i+3][j-1]+=1;
  47.             if(j-1==50-s) j--;
  48.         }   
  49.     }
  50.     common[2*i+3][0] = 50-j;
  51.  
  52.     if(common[2*i+2][0]>common[2*i][0])
  53.     s = common[2*i+2][0];
  54.     else s = common[2*i][0];
  55.  
  56.     for(j=50;50-s<j;j--) //좌우대칭타일 짝수부의피보나치 수열
  57.     {
  58.         common[2*i+4][j] =common[2*i+4][j] + common[2*i+2][j] + common[2*i][j];
  59.         if(common[2*i+4][j]>=10)
  60.         {
  61.             common[2*i+4][j]= common[2*i+4][j]-10;
  62.             common[2*i+4][j-1]+=1;
  63.             if(j-1==50-s) j--;
  64.         }   
  65.     }
  66.     common[2*i+4][0] = 50-j;    
  67. }
  68.  
  69.  
  70. for(i=3;i<=100;i++)  //총 만들수있는 타일의 경우의 수 계산
  71. {
  72.     if(A[i-1][0]>A[i-2][0])
  73.         s = A[i-1][0];
  74.     else s = A[i-2][0];
  75.  
  76.     for(j=50;50-s<j;j--)
  77.     {
  78.         A[i][j] = A[i][j] + A[i-1][j]+A[i-2][j];
  79.         if(A[i][j]>=10)
  80.         {
  81.             A[i][j] = A[i][j] -10;
  82.             A[i][j-1]+=1;
  83.             if(j-1==50-s) j--;
  84.         }
  85.     }
  86.     A[i][0] = 50-j;
  87. }
  88.  
  89. for(i=1;i<=C;i++)
  90. {              // 총 경우의 수와 대칭타일의 수를 뺌. 
  91.     t = in[i];
  92.     for(j=50;50-A[t][0]<j;j--)
  93.     {
  94.     if(A[t][j]>=common[t][j])
  95.         sol[t][j] = A[t][j]-common[t][j];
  96.  
  97.     else
  98.     {
  99.         A[t][j-1]-=1;
  100.         A[t][j] +=10;
  101.         sol[t][j] = A[t][j]-common[t][j];
  102.     }
  103.     }
  104.  
  105.     max=0;             
  106.     for(j=50;j>0;j--)  //빼고나서 sol의 숫자길이를 측정. 
  107.     {
  108.     if(sol[t][j]!=0) max=j;
  109.     }
  110.     if(max!=0)
  111.     sol[t][0] = 50-max+1;
  112.  
  113.     sum=0;
  114.     for(j=50-sol[t][0]+1;j<=50;j++) 
  115.     //1000000007로 나눈 나머지를 구함
  116.     {
  117.         sum+=sol[t][j];
  118.         if(sum>=1000000007)
  119.         {
  120.             sum=sum%1000000007;
  121.             if(j!=50)
  122.             sum=sum*10;
  123.         }
  124.         else
  125.         {
  126.             if(j!=50)
  127.             sum = sum*10;
  128.         }
  129.  
  130.     }
  131.     printf("%d\n",sum); //출력 
  132. }
  133.  
  134.  
  135.  
  136.  
  137. return 0;
  138.  
  139. }
Time limit exceeded #stdin #stdout 5s 3212KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/aLybRa
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!