/* 1 2 3 ... 26 27 28 29 ...52 53 ... 78 79 651 676 677 A B C ... Z AA AB AC ...AZ BA ... BZ CA ZA ZZ AAA 65 66 67 #include<stdio.h> void f(int n) { if(n==0) return ; f((n-1)/26); printf("%c", (n-1)%26+'A'); } int main() { int n; scanf("%d",&n); f(n); } */

/* #include<stdio.h> long long int memo[51][51]= {}; long long int f(int n,int m) { if(memo[n][m]!=0) return memo[n][m]; if(m==1||n==m) return memo[n][m]=1; return memo[n][m]=(f(n-1,m)+f(n-1,m-1))%100000000; } int main() { int n,i,j; scanf("%d",&n); for(i=1; i<=n; i++) { for(j=1; j<=i; j++) { printf("%lld ",f(i,j)); } printf("\n"); } return 0; } #include<stdio.h> int f(int n) { if(n==1) return 1; if(n==2) return 1; return f(n-1)+f(n-2); } int main() { int n; scanf("%d",&n); printf("%d",f(n)); return 0; } 1 2 3 ... 26 27 28 29 ...52 53 ... 78 79 ?? ?? ?? A B C ... Z AA AB AC ...AZ BA ... BZ CA ZA ZZ AAA 65 66 67 */ #include<stdio.h> int main() { int n,i; scanf("%d",&n); for(i=1;;i++) { if(n/26==0) break; // printf("%c",); } }

/* //memoization #include<stdio.h> int main() { int n,i,a,j,max=-10000000; int arr[100001]= {}; int memo[100001]= {}; //memo[i]= arr[i]까지의 연속 최대합 scanf("%d",&n); for(i=1; i<=n; i++) { scanf("%d",&arr[i]); } for(i=1; i<=n; i++) { memo[1]=arr[1]; if(memo[i-1]>0) memo[i]=memo[i-1]+arr[i]; else memo[i]=arr[i]; if(memo[i]>max) { max=memo[i]; } } printf("%d",max); } #include<stdio.h> int main() { int n,i; double max; double arr[10001]; double memo[10001]; scanf("%d",&n); for(i=1; i<=n; i++) { scanf("%lf",&arr[i]); } max=memo[1]=arr[1]; for(i=2; i<=n; i++) { if(memo[i-1]>1) memo[i]=memo[i-1]*arr[i]; else memo[i]=arr[i]; if(memo[i]>max) { max=memo[i]; } } printf("%.3lf",max); } */ #include<stdio.h> int memo[51][51]={}; int fib(int n,int m) { if(memo[n][m]!=0) return memo[n][m]; if(n==1||m==1) return memo[n][m]=1; return memo[n][m]=(fib(n-1,m)+fib(n,m-1))%100000000; } int main() { int n,i,j; scanf("%d",&n); for(i=1;i<=n;i++) { for(j=1;j<=i;j++) { printf("%d ",fib(i,j)); } printf("\n"); } return 0; }

/* queue 구현부분 #include <stdio.h> #define SIZE 50 int queue[SIZE]; int front=-1,rear=-1; void enqueue(int data) { //rear rear++; queue[rear]=data; } int dequeue() { //front : 데이터가 마지막으로 나간 위치 front++; return queue[front]; } int main() { } */ /* 바이러스 dfs풀이 #include<stdio.h> int arr[101][101]={},a[101]={},n; void dfs(int node) { for(int i=1;i<=n;i++) { if(arr[node][i]==1 && a[i]==0) { a[i]=1; dfs(i); } } } int main() { int b,c=0,x,y; scanf("%d %d",&n,&b); for(i=1;i<=b;i++) { scanf("%d %d",&x,&y); arr[x][y]=arr[y][x]=1; } dfs(1); for(i=2;i<=n;i++) { c+=a[i]; } printf("%d",c); } */ /*bfs로 바이러스 풀이*/ /* #include<stdio.h> int n,i; int queue[10001]; int front=-1,rear=-1; int arr[101][101]= {}; int a[101]= {}; void enqueue(int data) { rear++; queue[rear]=data; a[data]=1; } int dequeue() { front++; return queue[front]; } void bfs(int node) { for(i=1; i<=n; i++) { if(arr[node][i]==1 && a[i]==0) { enqueue(i); } } } int main() { int b,c=0,i,j,x,y; scanf("%d %d",&n,&b); for(i=1; i<=b; i++) { scanf("%d %d",&x,&y); arr[x][y]=arr[y][x]=1; } bfs(1); while(front!=rear) { bfs(dequeue()); } for(i=2; i<=n; i++) { c+=a[i]; } printf("%d",c); } */ /* //동적계획법 : 계산한 결과를 다시 계산하지 않도록 하는 방법 //재귀 메모이제이션 */ /* #include<stdio.h> int main() { int arr[100001],k,i,j,n,a,max,sum=0; scanf("%d %d",&n,&k); for(i=1; i<=n; i++) { scanf("%d",&arr[i]); } for(j=1; j<=k; j++) { sum+=arr[j]; } max=sum; for(i=1; i<n-k+1; i++) { sum=sum-arr[i]+arr[i+k]; if(sum>max) { max=sum; } } printf("%d",max); } */ #include<stdio.h> int main() { int arr[100001],n,i,sum=0,max=0; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&arr[i]); } if(sum>max) { sum=max; } }

/* #include<stdio.h> int arr[101][101]={},ar[101][101],cnt=0,cnt2=0,n,m; int dfs(int i,int j) { if(i<1||j<1||i>n||j>m||arr[i][j]!=1) return ; arr[i][j]=0; dfs(i-1,j); dfs(i+1,j); dfs(i,j-1); dfs(i,j+1); } int dfs2(int i,int j) { if(i<1||j<1||i>n||j>m||ar[i][j]!=0) return ; ar[i][j]=1; dfs2(i-1,j); dfs2(i+1,j); dfs2(i,j-1); dfs2(i,j+1); } int main() { int i,j; scanf("%d %d",&n,&m); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%d",&arr[i][j]); ar[i][j]=arr[i][j]; } } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(arr[i][j]==1) { cnt++; dfs(i,j); } } } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(ar[i][j]==0) { cnt2++; dfs2(i,j); } } } printf("%d %d",cnt2,cnt); } #include<stdio.h> int arr[101][101],ar[101][101],n,cnt=0; int dfs(int i,int j,int k) { if(i<1||j<1||i>n||j>n||arr[i][j]<=k) return ; arr[i][j]=0; dfs(i-1,j,k); dfs(i+1,j,k); dfs(i,j-1,k); dfs(i,j+1,k); } int main() { int i,j,k,max=1; scanf("%d",&n); for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { scanf("%d",&arr[i][j]); ar[i][j]=arr[i][j]; } } for(k=1; k<=100; k++) { for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { arr[i][j]=ar[i][j]; } } cnt=0; for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { if(arr[i][j]>k) { cnt++; dfs(i,j,k); } } } if(cnt>max) { max=cnt; } } printf("%d",max); } #include<stdio.h> int arr[8][8],cnt=0,n; int dfs(int i,int j,int c) { if(i<1||j<1||i>7||j>7||arr[i][j]!=c) return ; arr[i][j]=0; cnt++; dfs(i-1,j,c); dfs(i+1,j,c); dfs(i,j-1,c); dfs(i,j+1,c); } int main() { int i,j,area=0; for(i=1; i<=7; i++) { for(j=1; j<=7; j++) { scanf("%d",&arr[i][j]); } } for(i=1; i<=7; i++) { for(j=1; j<=7; j++) { if(arr[i][j]!=0) { cnt=0; dfs(i,j,arr[i][j]); if(cnt>=3) { area++; } } } } printf("%d",area); } #include<stdio.h> char arr[11][11]; int n,m,cnt=0; void dfs(int i,int j) { if(i<1||j<1||i>10||j>10||arr[i][j]!='_') return ; arr[i][j]='*'; dfs(i-1,j); dfs(i+1,j); dfs(i,j-1); dfs(i,j+1); } int main() { int i,j,area; for(i=1;i<=10;i++) { for(j=1;j<=10;j++) { scanf("%c ",&arr[i][j]); } } scanf("%d %d",&n,&m); dfs(m+1,n+1); for(i=1;i<=10;i++) { for(j=1;j<=10;j++) { printf("%c",arr[i][j]); } printf("\n"); } } */ /* queue 구현부분 #include <stdio.h> #define SIZE 50 int queue[SIZE]; int front=-1,rear=-1; void enqueue(int data) { //rear rear++; queue[rear]=data; } int dequeue() { //front : 데이터가 마지막으로 나간 위치 front++; return queue[front]; } int main() { } */ /* 바이러스 dfs풀이 #include<stdio.h> int arr[101][101]={},a[101]={},n; void dfs(int node) { for(int i=1;i<=n;i++) { if(arr[node][i]==1 && a[i]==0) { a[i]=1; dfs(i); } } } int main() { int b,c=0,x,y; scanf("%d %d",&n,&b); for(i=1;i<=b;i++) { scanf("%d %d",&x,&y); arr[x][y]=arr[y][x]=1; } dfs(1); for(i=2;i<=n;i++) { c+=a[i]; } printf("%d",c); } */ /*bfs로 바이러스 풀이*/ #include<stdio.h> int n; int queue[10001]; int front=-1,rear=-1; void enqueue(int data) { rear++; queue[rear]=data; } int dequeue() { front++; return queue[front]; } int main() { int b,c=0,x,y; scanf("%d %d",&n,&b); for(i=1;i<=b;i++) { } }

/* #include<stdio.h> int arr[101][101]= {},ar[101]= {},m,n,cnt=0; int dfs(int i,int j) { if(i<0||j<0||i>=m||j>=n||arr[i][j]!=0) return ; arr[i][j]=1; ar[cnt]++; dfs(i-1,j); dfs(i+1,j); dfs(i,j-1); dfs(i,j+1); } int main() { int i,j,k,a,b,c,d,t,temp; scanf("%d %d %d",&m,&n,&k); for(t=1; t<=k; t++) { scanf("%d %d %d %d",&a,&b,&c,&d); for(i=b; i<d; i++) { for(j=a; j<c; j++) { arr[i][j]=1; } } } for(i=0; i<m; i++) { for(j=0; j<n; j++) { if(arr[i][j]==0) { cnt++; dfs(i,j); } } } printf("%d\n",cnt); for(i=1;i<cnt;i++) { for(j=1;j<=cnt-i;j++) { if(ar[j]>ar[j+1]) { temp=ar[j]; ar[j]=ar[j+1]; ar[j+1]=temp; } } } for(i=1; i<=cnt; i++) { printf("%d ",ar[i]); } } #include<stdio.h> arr[101][101]= {},a[101]= {},cnt,n; void dfs(int i,int j) { if(i<1||j<1||i>n||j>n||arr[i][j]!=1) return ; arr[i][j]=0; a[cnt]++; dfs(i-1,j); dfs(i+1,j); dfs(i,j-1); dfs(i,j+1); } int main() { int i,j,k,t,temp; scanf("%d",&n); for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { scanf("%1d",&arr[i][j]); } } for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { if(arr[i][j]==1) { cnt++; dfs(i,j); } } } printf("%d\n",cnt); for(i=1; i<=cnt; i++) { for(j=1; j<=cnt-i; j++) { if(a[j]>a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } for(i=1; i<=cnt; i++) { printf("%d\n",a[i]); } } */ #include<stdio.h> int main() { int i,j,n,a; char str[101][101]={}; for(i=1;i<=10;i++) { for(j=1;j<=10;j++) { scanf("%c",&str[i][j]); } } scanf("%d %d",&n,&a); }

/* #include<stdio.h> int arr[101][101]= {},a[101]= {},n; void dfs(int node) { for(int i=1; i<=n; i++) { if(arr[node][i]==1 && a[i]==0) { a[i]=1; dfs(i); } } } int main() { int b,c=0,x,y,i; scanf("%d %d",&n,&b); for(i=1;i<=b;i++) { scanf("%d %d",&x,&y); arr[x][y]=arr[y][x]=1; } dfs(1); for(i=2; i<=n; i++) { c+=a[i]; } printf("%d",c); } #include<stdio.h> char str[101][101],c; void dfs(int i,int j) { if(str[i][j]!='L') return ; str[i][j]='.'; dfs(i-1,j); dfs(i,j-1); dfs(i+1,j); dfs(i,j+1); dfs(i-1,j-1); dfs(i+1,j-1); dfs(i+1,j+1); dfs(i-1,j+1); } int main() { int w,i,j,h,cnt=0; scanf("%d %d",&w,&h); for(i=1; i<=h; i++) { for(j=1; j<=w; j++) { scanf(" %c",&str[i][j]); } } for(i=1; i<=h; i++) { for(j=1; j<=w; j++) { if(str[i][j]=='L') { cnt++; dfs(i,j); } } } printf("%d",cnt); } */ /* #include<stdio.h> int arr[101][101]= {},n,m,cnt=0; int sd[10000]={}; void dfs(int i,int j) { if(i<0||j<0||j>=n||i>=m||arr[i][j]!=0) return ; arr[i][j]=1; sd[cnt]=cnt; dfs(i-1,j); dfs(i+1,j); dfs(i,j-1); dfs(i,j+1); } int main() { int k,i,j,a,b,c,d,cnt=0; scanf("%d %d %d",&m,&n,&k); while(k>0) { scanf("%d %d %d %d",&a,&b,&c,&d); for(j=a; j<c; j++) { for(i=b; i<d; i++) { arr[i][j]=1; } } k--; } for(i=0;i<m;i++) { for(j=0;j<n;j++) { if(arr[i][j]==0) { cnt++; dfs(i,j); } // printf("%d ",arr[i][j]); } //printf("\n"); } printf("%d\n",cnt); for(i=1;i<=cnt;i++) { printf("%d ",sd[i]); } } */ #include<stdio.h> int arr[101][101],n,cnt=0; int sd[10000]= {}; void dfs(int i,int j) { if(i<1||j<1||i>n||j>n||arr[i][j]!=0) return ; arr[i][j]=0; // sd[cnt]=cnt; dfs(i-1,j); dfs(i+1,j); dfs(i,j-1); dfs(i,j+1); } int main() { int i,j,temp,cnt=0,a; scanf("%d",&n); for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { scanf("%1d",&arr[i][j]); } } for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { if(arr[i][j]==1) { cnt++; dfs(i,j); } } } printf("%d",cnt); /* for(i=1;i<n;i++) { for(j=1;j<=n-i;j++) { if(arr[j]>arr[j+1]) { temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } */ }

/* #include<stdio.h> int stack[50001]; int top=-1; void push(int data) { top++; stack[top]=data; } int pop() { return stack[top--]; } int main() { char str[101],str1[101]; int i,sum,a,b,num,c=0,x,y; scanf("%s %s",str,str1); a=strlen(str)-1; b=strlen(str1)-1; while(a>=0||b>=0) { if(a==-1) x=0; else x=str[a--]-'0'; if(b==-1) y=0; else y=str1[b--]-'0'; num=x+y+c; push(num%10); c=num/10; } if(c!=0) push(c); while(top!=-1) { printf("%d",pop()); } } #include<stdio.h> int stack[50001]; int top=-1; void push(int data) { top++; stack[top]=data; } int pop() { return stack[top--]; } int main() { char str[201]; int i,a,b,num=0; gets(str); for(i=0;str[i]!=NULL;i++) { if(48<=str[i]&&str[i]<=57) { num=num*10+str[i]-'0'; if(str[i+1]==' ') { push(num); num=0; } } else if(str[i]=='+') { a=pop(); b=pop(); push(b+a); } else if(str[i]=='-') { a=pop(); b=pop(); push(b-a); } else if(str[i]=='*') { a=pop(); b=pop(); push(b*a); } } printf("%d",pop()); return 0; } */ /* #include <stdio.h> #define SIZE 50 int queue[SIZE]; int front=-1,rear=-1; void enqueue(int data) { //rear rear++; queue[rear]=data; } int dequeue() { //front : 데이터가 마지막으로 나간 위치 front++; return queue[front]; } int main() { } */ #include<stdio.h> int arr[101][101]={},a[101]={},n; void dfs(int node) { for(int i=1;i<=n;i++) { if(arr[node][i]==1 && a[i]==0) { a[i]=1; dfs(i); } } } int main() { int b,c=0,x,y; scanf("%d %d",&n,&b); for(i=1;i<=b;i++) { scanf("%d %d",&x,&y); arr[x][y]=arr[y][x]=1; } dfs(1); for(i=2;i<=n;i++) { c+=a[i]; } printf("%d",c); }

/* #include<stdio.h> int stack[200]; int top=-1; //마지막으로 입력된 데이터의 위치 pop() { if(top==-1) return -1; return stack[top--]; } main() { int n,i,j,num=0; char str[50]; scanf("%d ",&n); for(i=1;i<=n;i++) { gets(str); if(str[1]=='u') { num=0; for(j=6;str[j]!=' ';j++) { num=num*10+str[j]-'0'; } top++; stack[top]=num; } else if(str[0]=='t') { if(top==-1) { printf("-1\n"); } else { printf("%d\n",stack[top]); } } else if(str[0]=='e') { if(top==-1) { printf("true\n"); } else { printf("false\n"); } } else if(str[0]=='s') { printf("%d\n",top+1); } else { pop(); } } } 3+3+1+3+1+2+1+1+1 #include<stdio.h> int top=0; // 놓여있는 쇠막대기의 개수 int main() { int i,n,sum=0,num=0; char str[100001]; scanf("%s",str); for(i=0; str[i]!=NULL; i++) { if(str[i]=='(') { if(str[i+1]==')') { sum+=top; i++; } else { top++; } } else { top--; sum++; } } printf("%d",sum); } #include<stdio.h> int stack[50001]; int top=-1; void push(int data) { top++; stack[top]=data; } int pop() { if(top==-1) return -1; return stack[top--]; } int main() { char str[50001]; int i; scanf("%s",str); for(i=0; str[i]!=NULL; i++) { if(str[i]=='(') { push(1); } else { if(top==-1) { printf("bad"); return 0; } pop(); } } if(top==-1) { printf("good"); } else { printf("bad"); } } */

/* #include <stdio.h> int stack[7]; int top=-1; // 마지막으로 입력된 데이터의 위치 void push(int data) { top++; stack[top]=data; } int pop() { return stack[top--]; } int main() { push(3); push(4); push(5); printf("%d",pop()); printf("%d",pop()); } #include<stdio.h> int stack[200]; int top=-1; void push(int data) { top++; stack[top]=data; } int pop() { return stack[top--]; } int main() { int n,i,t; int a[201]={}; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%1d",&a[i]); } for(i=n;i>=1;i--) { push(a[i]); } while(top!=-1) { printf("%d",pop()); if((top+1)%3==0&&top!=n-1&&top!=-1) { printf(","); } } } #include<stdio.h> int stack[100000]; int top=-1; void push(int data) { top++; stack[top]=data; } int pop() { return stack[top--]; } int main() { int n,i,t,s=0; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&t); if(t==0) { pop(); } else { push(t); } } while(top!=-1) { s+=pop(); } printf("%d",s); } #include<stdio.h> int stack[100]; int top=-1; void push(int data) { top++; stack[top]=data; } int pop() { return stack[top--]; } int main() { int i; char str[50]; scanf("%s",str); for(i=0; str[i]!=NULL ; i++) { push(str[i]-'0'); } while(top!=-1) { printf("%d",pop()); } } #include<stdio.h> int stack[101]; int top=-1; void push(int data) { top++; stack[top]=data; } int pop() { return stack[top--]; } int main() { char s[101],a[101]; int i,ls,la,num,c=0; scanf("%s %s",s,a); ls=strlen(s)-1; la=strlen(a)-1; for(i=ls;i>=ls-la;i--) { num=s[i]+a[i-ls+la]-'0'*2+c; push(num%10); c=num/10; } for(i=ls-la+1;i>=0;i--) { num=s[i]+c-'0'; push(num%10); c=num/10; } if(c!=0) push(c); while(top!=-1) { printf("%d",pop()); } } */

/* #include<stdio.h> int a[10001]; //quick_sort void swap(int x, int y) { int t=a[x]; a[x]=a[y]; a[y]=t; } void qs(int start, int end) { int pivot=start, low=start, high=end+1; if(start>=end) return ; do { do { low++; }while(a[pivot]>a[low]); do { high--; } while(a[pivot]<a[high]); if(low<high) swap(low,high); }while(low<high); swap(high,pivot); qs(start,high-1); qs(high+1,end); } int main() { int n,i; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } qs(1,n); for(i=1;i<=n;i++) { printf("%d\n",a[i]); } } #include<stdio.h> int a[100001]; int b[100001]; void swap(int x, int y) { int t=a[x]; a[x]=a[y]; a[y]=t; } void qs(int start, int end) { int pivot=start, low=start, high=end+1; if(start>=end) return ; do { do { low++; }while(a[pivot]>a[low]); do { high--; } while(a[pivot]<a[high]); if(low<high) swap(low,high); }while(low<high); swap(high,pivot); qs(start,high-1); qs(high+1,end); } int bs(int s,int e,int k) { int mid=(s+e)/2; if(s>e) return -1; if(a[mid]==k) return mid; else if(a[mid]<k) bs(mid+1,e,k); else bs(s,mid-1,k); } int main() { int n,i,j; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]; } qs(1,n); for(i=1;i<=n;i++) { printf("%d ",bs(1,n,b[i])-1); } return 0; } */ /* #include<stdio.h> void f(int* pa) { *pa=100; } int main() { int a; int* pa; scanf("%d",&a); printf("%d\n",a); // pa=&a; f(&a); printf("%d\n",a); // printf("%d\n",pa); // printf("%d\n",*pa); // f(a,b); //printf("%d %d",a,b); return 0; } */ /* #include <stdio.h> void myswap(int* pa,int* pb) { int t; if(*pa>*pb) { t=*pa; *pa=*pb; *pb=t; } } main() { int a, b; scanf("%d%d", &a, &b); myswap(&a, &b); printf("%d %d", a, b); } #include<stdio.h> double f(double n) { if(n<0) { n=-n; } return n; } int main() { double n; scanf("%lf", &n); printf("%.10g", f(n)); return 0; } #include<stdio.h> char* mysubstr(char* str, int start, int count) { *(str+start+count)=NULL; return str+start; } int main() { char str[101]={}; int a,b; scanf("%s %d %d",str,&a,&b); printf("%s",mysubstr(str,a,b)); return 0; } */

/* #include<stdio.h> int main() { int i,sum=10; char st[51]={}; scanf("%s",st); for(i=1;st[i]!=NULL;i++) { if(st[i]==st[i-1]) { sum=sum+5; } else { sum=sum+10; } } printf("%d",sum); return 0; } #include<stdio.h> int main() { int n,i,a=0,b=1; for(i=1;i<=9;i++) { scanf("%d",&n); if(a<n) { a=n; b=i; } } printf("%d\n%d",a,b); return 0; } #include <stdio.h> int memo[201]={}; int fib(int n) { if(memo[n]!=0) return memo[n]; //한 번 계산한 값은 다시 계산하지 않는다. //시간이 단축된다 !! if(n==1||n==2) return memo[n]=1; return memo[n]=(fib(n-1)+fib(n-2)); } int main() { int n; scanf("%d",&n); printf("%d",fib(n)); return 0; } #include<stdio.h> int memo[51][51]={}; int fib(int n,int m) { if(memo[n][m]!=0) return memo[n][m]; if(n==1||m==1) return memo[n][m]=1; return memo[n][m]=(fib(n-1,m)+fib(n,m-1))%100000000; } int main() { int n,m; scanf("%d %d",&n,&m); printf("%d",fib(n,m)); return 0; } */ //이분탐색 이진탐색 //binary search /* #include<stdio.h> int a[50]; int bs(int s, int e, int k) { int mid=(s+e)/2; if(s>e) return -1; if(a[mid]==k) return mid; else if(a[mid]<k) bs(mid+1,e,k); else bs(s,mid-1,k); } #include<stdio.h> int a[1000001]; int bs(int s,int e,int k) { int mid=(s+e)/2; if(s>e) return -2; if(a[mid]==k) return mid; else if(a[mid]<k) bs(mid+1,e,k); else bs(s,mid-1,k); } int main() { int n,m,i,k; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&a[i]); } scanf("%d",&m); for(i=0;i<m;i++) { scanf("%d",&k); printf("%d ",bs(0,n-1,k)+1); } return 0; } */ #include<stdio.h> int a[100001],n; int bs(int s,int e,int k) { int mid=(s+e)/2; if(s>=e) { if(a[mid]>=k) return mid; else return n+1; } if(a[mid]>=k) bs(s,mid,k); else bs(mid+1,e,k); } int main() { int i,k; scanf("%d %d",&n,&k); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } printf("%d",bs(1,n,k)); return 0; }

/* #include<stdio.h> void f(int n) { if(n==1) { printf("%d\n",n); return ; } if(n%2==1) { f(3*n+1); } else { f(n/2); } printf("%d\n",n); } int main() { int n; scanf("%d",&n); f(n); } #include<stdio.h> int f(int n) { if(n==1) return 1; return f(n-1)+n; } int main() { int n; scanf("%d",&n); printf("%d",f(n)); } #include<stdio.h> int f(int n) { if(n==1) return 1; return f(n-1)*n; } int main() { int n; scanf("%d",&n); printf("%d",f(n)); } #include<stdio.h> int f(int n) { if(n==1) return 1; if(n==2) return 1; return f(n-1)+f(n-2); } int main() { int n; scanf("%d",&n); printf("%d",f(n)); return 0; } #include<stdio.h> void f(int n) { if(n==0) return ; printf("*"); f(n-1); } void f1(int n) { if(n==0) return ; f1(n-1); f(n); printf("\n"); } int main() { int n; scanf("%d",&n); f1(n); } #include<stdio.h> void f(int n) { if(n==0) return ; f(n/2); printf("%d",n%2); } int main() { int n; scanf("%d",&n); if(n==0) { printf("0"); return 0; } f(n); return 0; } #include<stdio.h> int main() { int sum=0,n,i,a,k=1; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a); if(a==1) { sum+=k; k++; } else { k=1; } } printf("%d",sum); return 0; } */

/* #include<stdio.h> typedef struct { int n1,s1,s2; } s; int main() { s st[1001],temp; int n,i,j; scanf("%d",&n); for(i=1; i<=n; i++) { scanf("%d %d",&st[i].s1,&st[i].s2); st[i].n1=i; } for(i=1; i<n; i++) { for(j=1; j<=n-i; j++) { if(st[j].s1<st[j+1].s1) { temp=st[j]; st[j]=st[j+1]; st[j+1]=temp; } else if(st[j].s1==st[j+1].s1) { if(st[j].s2<st[j+1].s2) { temp=st[j]; st[j]=st[j+1]; st[j+1]=temp; } else if(st[j].s2==st[j+1].s2) { if(st[j].n1>st[j+1].n1) { temp=st[j]; st[j]=st[j+1]; st[j+1]=temp; } } } } } for(i=1;i<=n;i++) { printf("%d %d %d\n",st[i].n1,st[i].s1,st[i].s2); } return 0; } f(n) : *을 n번 출력 *을 출력 --> *을 n-1 번 출력 *출력 --> f(n-1) #include <stdio.h> void f(int n) { if(n==0) return ; printf("*"); f(n-1); } int main() { f(3); printf("hello world"); f(5); return 0; } f(n) : n부터 1까지 출력 n출력 --> n-1부터 1까지 출력 n출력 --> f(n-1) #include<stdio.h> void f(int n) { if(n==0) return ; printf("%d\n",n); f(n-1); } int main() { int n; scanf("%d",&n); f(n); } #include<stdio.h> void f(int n) { if(n==0) return ; f(n-1); printf("%d\n",n); } int main() { int n; scanf("%d",&n); f(n); } f(n) : 1부터 n까지 출력 1부터 n-1까지 출력 --> n출력 f(n-1)--> n출력 f(a,b) : a부터 b까지 출력 a부터 b-1까지 출력 --> b출력 f(a,b-1)--> b출력 #include<stdio.h> void f(int a,int b) { if(a>b) return ; f(a,b-1); if(b%2==1) printf("%d ",b); } int main() { int a,b; scanf("%d %d",&a,&b); f(a,b); } #include <stdio.h> void f(int n) { printf("%d\n",n); if(n==1) return ; if(n%2==1) { f(3*n+1); } else { f(n/2); } } int main() { int n; scanf("%d",&n); f(n); } */

/* #include<stdio.h> typedef struct { int s1,s2,s3; } score; int main() { score st[1001]; int c[3]; int n,i,j,mi; scanf("%d",&n); for(i=0; i<n; i++) { scanf("%d %d %d",&st[i].s1,&st[i].s2,&st[i].s3); } for(j=0; j<3; j++) { if(j==2 && c[0]==c[1]) { for(i=0;i<n;i++) { if(st[i].s1==c[0]) { st[i].s3=0; } } } mi=0; for(i=0; i<=n; i++) { if(st[mi].s3<st[i].s3) { mi=i; } } printf("%d %d\n",st[mi].s1,st[mi].s2); st[mi].s3=0; c[j]=st[mi].s1; } } #include<stdio.h> typedef struct { int s,d; }cd; int main() { cd st[10001],temp; int a,b,n,i,j; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d %d",&st[i].s,&st[i].d); } for(i=1; i<n; i++) { for(j=1; j<=n-i; j++) { if(st[j].s>st[j+1].s) { temp=st[j]; st[j]=st[j+1]; st[j+1]=temp; } } } for(i=1;i<=n;i++) { printf("%d %d\n",st[i].s,st[i].d); } return 0; } #include<stdio.h> typedef struct { char a[100]; int b,c,d; } ab; int main() { ab st[101],temp; int n,i,j; scanf("%d",&n); for(i=1; i<=n; i++) { scanf("%s %d %d %d",st[i].a,&st[i].b,&st[i].c,&st[i].d); } for(i=1; i<n; i++) { for(j=1; j<=n-i; j++) { if(st[j].b>st[j+1].b) { temp=st[j]; st[j]=st[j+1]; st[j+1]=temp; } else if(st[j].b==st[j+1].b) { if(st[j].c>st[j+1].c) { temp=st[j]; st[j]=st[j+1]; st[j+1]=temp; } else if(st[j].c==st[j+1].c) { if(st[j].d>st[j+1].d) { temp=st[j]; st[j]=st[j+1]; st[j+1]=temp; } else if(st[j].d==st[j+1].d) { if(strcmp(st[j].a,st[j+1].a)>0) { temp=st[j]; st[j]=st[j+1]; st[j+1]=temp; } } } } } } for(i=1; i<=n; i++) { printf("%s\n",st[i].a); } return 0; } a*b == gcd(a,b)*최소공배수 #include <stdio.h> int gcd(int p, int q){ if(p==0) return q; return gcd(q%p, p);} long long int lcm(int a,int b) { return (long long int)a*b/gcd(a,b); } int main() { int a, b; scanf("%d%d", &a, &b); printf("%lld\n", lcm(a, b)); } #include <stdio.h> int n, a, b, d[1010]; int maxi(int a,int b) { int mi,i; mi=a; for(i=a;i<=b;i++) { if(d[mi]<d[i]) { mi=i; } } return mi; } int main() { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &d[i]); scanf("%d%d", &a, &b); printf("%d\n", maxi(a, b)); } */

/* #include<stdio.h> int a[10001]; int n,i,j,temp; int main() { for(i=1; i<=3; i++) { scanf("%d",&a[i]); } for(i=1; i<3; i++) { for(j=1; j<=3-i; j++) { if(a[j]>a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } for(i=1;i<=3;i++) { printf("%d ",a[i]); } return 0; } #include<stdio.h> int a[8]; int n=7,i,j,temp; int main() { for(i=1;i<=n;i++) { scanf("%d",&a[i]); } for(i=1;i<n;i++) { for(j=1;j<=n-i;j++) { if(a[j]<a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } for(i=1;i<=2;i++) { printf("%d\n",a[i]); } return 0; } #include <stdio.h> int a[10001]; int n, i, j, temp, min; int main() { scanf("%d", &n); for (i = 1; i <= n; i++) scanf("%d", &a[i]); for (i=1; i<n; i++) { min=i; //min = 가장 작은 값이 있는 위치 for (j=i+1; j<=n; j++) { if(a[min]>a[j]) { min=j; } } temp = a[i]; a[i] = a[min]; a[min] = temp; } for (i=1; i<=n; i++) printf("%d\n", a[i]); return 0; } #include <stdio.h> int a[10001]; int n, i, j, temp, key; int main() { scanf("%d", &n); for (i = 1; i <= n; i++) scanf("%d", &a[i]); for (i=2; i<=n; i++) { key=a[i]; for(j=i-1;j>=1&&key<a[j];j--) { a[j+1]=a[j]; } a[j+1]=key; } for (i=1; i<=n; i++) printf("%d\n", a[i]); return 0; } */ /* //구조체 : 내가 정의한 자료형 #include <stdio.h> typedef struct { int num; float grade; char b; }student; int main() { student a[100]; scanf("%d",&a[1].num); a.num=1; a.grade=4.0; } #include<stdio.h> typedef struct { char name[20]; int s1, s2, s3; }a; int main() { a st[101]; int n,i,mi,b=1,c=1; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%s %d %d %d",st[i].name,&st[i].s1,&st[i].s2,&st[i].s3); } mi=1; for(i=1;i<=n;i++) { if(st[mi].s1<st[i].s1) { mi=i; } } printf("%s",st[mi].name); for(i=1;i<=n;i++) { if(st[mi].s2<st[i].s2) { b++; } if(st[mi].s3<st[i].s3) { c++; } } printf(" %d %d",b,c); return 0; } 3015 4751 #include<stdio.h> typedef struct { char name[11]; int s; } score; int main() { score st[101],temp; int n,m,i,j; scanf("%d %d",&n,&m); for(i=1; i<=n; i++) { scanf("%s %d",st[i].name,&st[i].s); } for(i=1; i<n; i++) { for(j=1; j<=n-i; j++) { if(st[j].s<st[j+1].s) { temp=st[j]; st[j]=st[j+1]; st[j+1]=temp; } } } for(i=1; i<=m; i++) printf("%s\n",st[i].name); return 0; } */

/* #include<stdio.h> int main() { int a,b,c; scanf("%d %d %d",&a,&b,&c); printf("%d %d",(a+(b+c)/60)%24,(b+c)%60); return 0; } #include <stdio.h> int a[10001]; int n, i, j, temp,flag=0; int main() { scanf("%d", &n); for (i=1; i<=n; i++) scanf("%d", &a[i]); if(n==2 && a[1]>a[2]) { printf("1"); return 0; } for(i=1; i<n; i++) { flag=0; for(j=1;j<=n-i;j++) { if (a[j] > a[j+1]) { flag=1; temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } if(flag==0) { printf("%d",i-1); return 0; } } } #include <stdio.h> int a[10001]; int n, i, j, temp; int main() { scanf("%d", &n); for (i=1; i<=n; i++) scanf("%d", &a[i]); for(i=1; i<n; i++) { for(j=1;j<=n-i;j++) { if (a[j] > a[j+1]) { temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } for (i = 1; i <= n; i++) printf("%d\n", a[i]); return 0; } #include <stdio.h> int a[10001]; int n, i, j, temp,flag=0; int main() { scanf("%d", &n); for (i=1; i<=n; i++) scanf("%d", &a[i]); if(n==2 && a[1]>a[2]) { printf("1"); return 0; } for(i=1; i<n; i++) { flag=0; for(j=1;j<=n-i;j++) { if (a[j] > a[j+1]) { flag=1; temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } if(flag==0) { printf("%d",i-1); return 0; } } } #include <stdio.h> int a[10001]; int n, i, j, temp; int main() { scanf("%d", &n); for (i=1; i<=n; i++) scanf("%d", &a[i]); for(i=1; i<n; i++) { for(j=1;j<=n-i;j++) { if (a[j] > a[j+1]) { temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } for (i = n; i >= 1; i--) printf("%d ", a[i]); return 0; } #include <stdio.h> int a[10001]; int n, i, j, temp; int main() { scanf("%d", &n); for (i=1; i<=n; i++) scanf("%d", &a[i]); for(i=1; i<n; i++) { for(j=1;j<=n-i;j++) { if (a[j] < a[j+1]) { temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } for (i = 1; i <= n; i++) printf("%d ", a[i]); return 0; } */

/* #include<stdio.h> int main() { int n,a,b,c,d,e; scanf("%d-%d",&n,&a); b=n/10000; c=n/100%100; d=n%100; e=a/1000000; if(e==1||e==2) { printf("19%02d/%02d/%02d", b, c, d); } else { printf("20%02d/%02d/%02d", b, c, d); } if(e==1||e==3) { printf(" M"); } else { printf(" F"); } return 0; } #include<stdio.h> int main() { int a,b,i,n,sum=0,s=0; scanf("%d",&n); for(;;) { sum+=n%10; s += n%10; n=n/10; if(n==0) { printf("%d\n",sum); printf("%d\n",s); break; } sum=sum*10; } return 0; } */ #include<stdio.h> int n; int f() { int i; scanf("%d",&n); for(i=1;i<=n;i++) { } } int main() { }

/* #include <stdio.h> int a, b; int gcd(int a,int b) { int i; int n = a>b ? b : a; for(i=n; i>=1; i--) { if(a%i==0&&b%i==0) { return i; } } } // 이 부분에 들어가야 될 코드를 작성하여 제출 int main() { scanf("%d%d", &a, &b); printf("%d\n", gcd(a, b)); } #include<stdio.h> int main() { int a, b; scanf("%d %d",&a,&b); printf("%d",a>b?a:b); } #include <stdio.h> int n, k, d[1010]; int findi(int k) { int i; for(i=1;i<=n;i++) { if(d[i]==k) { return i; } } return -1; } // 이 부분에 들어가야 될 코드를 작성하여 제출 int main() { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &d[i]); scanf("%d", &k); printf("%d\n", findi(k)); } #include <stdio.h> int n, d[100010], k; int f(int k) { int i; for(i=1;i<=n;i++) { if(d[i]==k) { return i; } } return -1; } // 이 부분에 들어가야 될 코드를 작성하여 제출 int main() { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &d[i]); scanf("%d", &k); printf("%d\n", f(k)); } #include <stdio.h> int n, k, d[1010]; int upper_bound(int k) { int i; for(i=1; i<=n; i++) { if(k<d[i]) { return i; } } return n+1; } // 이 부분에 들어가야 될 코드를 작성하여 제출 int main() { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &d[i]); scanf("%d", &k); printf("%d\n", upper_bound(k)); } #include <stdio.h> int n; long long int f(int n) { int i; long long int sum=0; for(i=1;i<=n;i++) { sum+=i; } return sum; } // 이 부분에 들어가야 될 코드를 작성하여 제출 int main() { scanf("%d", &n); printf("%lld\n", f(n)); } #include <stdio.h> int n, a, b, d[1010]; long long int subsetsum(int a,int b) { int i; long long int sum=0; for(i=a;i<=b;i++) { sum+=d[i]; } return sum; } // 이 부분에 들어가야 될 코드를 작성하여 제출 int main() { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &d[i]); scanf("%d%d", &a, &b); printf("%lld\n", subsetsum(a, b)); } #include <stdio.h> int n, d[110]; int f() { int i; int max=d[0],mi=0; for(i=0;i<n;i++) { if(max<d[i]) { max=d[i]; mi=i; } } return mi+1; } // 이 부분에 들어가야 될 코드를 작성하여 제출 int main() { scanf("%d", &n); for(int i=0; i<n; i++) scanf("%d", &d[i]); printf("%d", f()); return 0; } #include <stdio.h> int a, n; long long int pow(int a,int n) { int i; long long int sum=1; if(a==1) return sum; for(i=1;i<=n;i++) { sum*=a; } return sum; } // 이 부분에 들어가야 될 코드를 작성하여 제출 int main() { scanf("%d%d", &a, &n); printf("%lld\n", pow(a, n)); } #include <stdio.h> int n; long long int d[110]; long long int f() { int i; long long int min=d[1]; for(i=1;i<=n;i++) { if(min>d[i]) { min=d[i]; } } return min; } // 이 부분에 들어가야 될 코드를 작성하여 제출 int main() { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%lld", &d[i]); printf("%lld", f()); return 0; } */ /* #include <stdio.h> long long int n; long long int f(long long int n) { int i; long long int rev=0; for(;;) { if(n==0) { break; } rev=rev*10+n%10; n=n/10; } return rev; } // 이 부분에 들어가야 될 코드를 작성하여 제출 int main() { scanf("%lld", &n); printf("%lld\n", f(n)); } */

/* #include<stdio.h> int main() { int n,i,j,sum=0,k=1; int a[101][101]; scanf("%d",&n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { a[i][j]=k++; if(i==1||i==n||j==1||j==n) { sum+=k-1; } } } printf("%d",sum); return 0; } #include<stdio.h> int main() { int n,i,j,r,c,cnt,ii,jj; int arr[27][27]= {}; for(i=1; i<=25; i++) { for(j=1; j<=25; j++) { scanf("%d",&arr[i][j]); } } for(i=1; i<=25; i++) { for(j=1; j<=25; j++) { cnt=0; for(ii=i-1; ii<=i+1; ii++) { for(jj=j-1; jj<=j+1; jj++) { cnt+=arr[ii][jj]; } } if(arr[i][j]==0) { if(cnt==3) { printf("1 "); } else { printf("0 "); } } else { cnt--; if(cnt>=4||cnt<=1) { printf("0 "); } else if(cnt==2||cnt==3) { printf("1 "); } } } printf("\n"); } return 0; } #include<stdio.h> int n,i,j,h,w,l,d,x,y; int arr[101][101]= {}; void f(int m) { int k; for(k=1; k<=m; k++) { for(i=1; i<=h; i++) { for(j=1; j<=w; j++) { printf("%d ",arr[i][j]); } printf("\n"); } } } int main() { scanf("%d %d %d",&h,&w,&n); for(i=1; i<=n; i++) { scanf("%d %d %d %d",&l,&d,&x,&y); for(j=0; j<l; j++) { arr[x][y]=1; if(d==0) { y++; } else { x++; } } } f(8); return 0; } */ /* #include<stdio.h> char f(int n) { return 'a'; } int main() { printf("%c",f(10)); return 0; } */ /* #include <stdio.h> int main() { f(); return 0; } #include <stdio.h> // 이 부분에 들어가야 될 코드를 작성하여 제출 void f() { printf("hello"); } int main() { f(); return 0; } #include <stdio.h> // 이 부분에 들어가야 될 코드를 작성하여 제출 char f() { return 'A'; } int main() { printf("%c", f() ); return 0; } #include <stdio.h> int n; void f(int n) { if(n%2==1) { printf("odd"); } else { printf("even"); } } // 이 부분에 들어가야 될 코드를 작성하여 제출 int main() { scanf("%d", &n); f(n); return 0; } #include <stdio.h> int n; void f(int n) { int i; for(i=1;i<=n;i++) { printf("*"); } } // 이 부분에 들어가야 될 코드를 작성하여 제출 int main() { scanf("%d", &n); f(n); return 0; }#include <stdio.h> int n; char grade(int n) { if(100>=n&&n>=90) { return 'A'; } else if(80<=n) { return 'B'; } else if(70<=n) { return 'C'; } else if(60<=n) { return 'D'; } else { return 'F'; } } // 이 부분에 들어가야 될 코드를 작성하여 제출 int main() { scanf("%d", &n); printf("%c", grade(n)); return 0; } #include <stdio.h> long long int n; long long int abs(long long int n) { if(n<0) { n=-n; } return n; } // 이 부분에 들어가야 될 코드를 작성하여 제출 int main() { scanf("%lld", &n); printf("%lld\n", abs(n)); return 0; } #include <stdio.h> int n; int f(int n) { int i,sum=0; for(i=1;i<=n;i++) { if(n%i==0) { sum++; } } return sum; } // 이 부분에 들어가야 될 코드를 작성하여 제출 int main() { scanf("%d", &n); printf("%d\n", f(n)); } */