ACM 합숙 훈련 day1

7.11
요점: 0.매거법최대 공인수 구하기 2.기억화 사상
note: 시간 복잡도 계산에 능하다
0
1
매거법
분류 매거, 폭력
최대 공인수를 구하다
전전상제>발산->최소 공배수
기억화 사상
예처리, 접두어와 사상
사고문제 0.0:
피보나치 수열과 전전 상제법의 상관성을 지적하고, 전전 상제법의 시간 복잡도를 대체적으로 분석하였다.
사고문제 0.1:

             
#include 
using namespace std;

int fib(int n)
{
    if (n==0 || n==1) return 1;
    int ans=fib(n-2)+fib(n-1);
    return ans;
}

int main()
{
    int n; 
    scanf("%d",&n);
    printf("%d
",fib(n));
    return 0;
}

==========================나는 분할선 ====================================
연습 문제
A번 Least Common Multiple
**사고방식: 서로 인접한 두 수의 최소 공배수를 구하고, 세 번째 수와 최소 공배수를 구하며, 이렇게 끝날 때까지 반복한다.

#include
#include
#include
using namespace std;
int gcd(int a,int b);
int main()
{
    int n,m;
    scanf("%d",&n);
    while(n--)
    {
        int a[100];
        int i;
        scanf("%d",&m);
        for(i=0;iscanf("%d",&a[i]);
        for(i=1;i1])*a[i-1];//**     =    /     **（         ），   a[i]

        }
        printf("%d
",a[i-1]);

    }
    return 0;
}
int gcd(int a,int b) //           
{

    if(a//     ，       a>b
        swap(a,b);
    while(b!=0)   
    {
        int t;
        t=a;
        a=b;
        b=t%b;
    }
    if(b==0)
        return a;
}

==========================나는 분할선 ====================================
B 진수 변환
사고방식: 10진법을 회상하여 2진법으로 바꾸고 2로 나눈 것을 2로 나눈 것을... 거꾸로 출력하는 것과 같은 이치

#include

int main()
{
   int n,r,a[1000];
   while(scanf("%d %d",&n,&r)!=EOF)
   {
       int i,j;
       int tag=1;
       if(n<0)        //    ，      ，        
       {
            n=(-1)*n;
          tag=0;
       }
       for(i=0;n!=0;i++) //       
       {
           a[i]=n%r;
           n/=r;
       }
        if(tag==0)
            printf("-");    //       -
       for(j=i-1;j>=0;j--)        //    
       {
           if(a[j]>=10)
           {
               switch(a[j])
           {
               case 10:printf("A");break;   //      ，  16      ，    'A'+i
               case 11:printf("B");break;
               case 12:printf("C");break;
               case 13:printf("D");break;
               case 14:printf("E");break;
               case 15:printf("F");break;
               default:break;
           }
           continue;
           }
           printf("%d",a[j]);
       }

        printf("
");
   }

    return 0;
}

==========================나는 분할선 ====================================
C 문제
이 문제는 더 이상 드릴 말씀이 없는데... 그냥 멀뚱멀뚱 정수를 정수로 보고 와~ 233!

#include

int main()
{
    int i,n;
    scanf("%d",&n);
    for(i=0;idouble a,b,c;
        scanf("%lf%lf%lf",&a,&b,&c);
        if(a+b>c&&a+c>b&&b+c>a&&a&&b&&c)
            printf("YES
");    //**    （  E ）    “Yes”，     ！**
        else
            printf("NO
");
    }
    return 0;

==========================나는 분할선 ====================================
D번 빈 삼각형
** note: 한 문자를 여러 번 읽으면 오류 발생

#include
#include
#include

int main()
{
   int gao;
   char hua,str[10];
   int test=0;
   while(1)
   {
       scanf("%s",str);  //       %c，                   ，      ，    。**      ，                ！**
       hua=str[0];
       if(hua=='@')
        return 0;
        else
            if (test) printf("
"); //**       **  @       ，              
       test++;

       scanf("%d",&gao);



       int i,j,k;
       for(i=0;iif(i==gao-1)
           {
               for(k=0;k<2*gao-1;k++)
               printf("%c",hua);
                printf("
");
           }

           else
           {
               for(j=0;j1;j++)
                    printf(" ");
                printf("%c",hua);

                if(i==0)
                {
                    printf("
");
                    continue;
                }
                for(j=0;j<2*i-1;j++)
                    printf(" ");
                printf("%c
",hua);
           }
       }

       //fflush(stdin); //   judge      ，    ，

   }
    return 0;
}

==========================나는 분할선 ====================================
E제
note: 제목을 유의해서 무엇을 출력하라고!YES?!Yes?!yes?!

#include

int main()
{
    int a,b,i;
     while(scanf("%d%d",&a,&b)&&(a||b))
    {
            int tag=0;
            for(i=-10000;i<10000;i++)

            if((a-i)*i==b)
            {
                 printf("Yes
");
                 tag=1;
                 break;
            }
        if(tag==0)
            {
                printf("No
");

            }

    }
    return 0;
}

F문제는 A가 안 나왔는데... TAT...========================나는 분할선=========================================
G 제
사고방식: 함수 판단 예쁜 수->정의 수조는 1부터 i까지의 예쁜 수 총수를 나타낸다->기억화 사상->지정 구간

#include
#include
#include
#include
#include
using namespace std;

int Isbeauty(int x);

int main()
{
    int n,sum[100001]={0};//   i    
    scanf("%d",&n);

    for(int i=1;i<=100000;i++) //**i 1  **
    {
        sum[i]=sum[i-1]+Isbeauty(i);  **//     ，       ，      1         **
    }
    while(n--)
    {
        int l,r;
        scanf("%d %d",&l,&r);

        printf("%d
",sum[r]-sum[l-1]); //[l,r]   

    }
    return 0;
}

int Isbeauty(int x)  //       
{
    int a[11]={0};

    while(x!=0)
    {
        if(a[x%10])  //       
            return 0;  //  0，     
        else
            a[x%10]++;  
        x/=10;      
    }
    return 1;  //      ，  1，    
}

좀 바빠서 못 하겠네요, 당일 연습 미처 정리하지 못했는데...좋은 출발 하시고 ACM길에서 더욱 강해지세요~