/* #include <stdio.h> int ar[100000]={}; int sum=0; int n,m=0,a=0; int bs(int k) { m=m+ar[a]; if (m==k) sum++; } int main() { int i,k; scanf("%d %d", &n,&k); for (i=0; i<n; i++) { scanf("%d",&ar[i]); } for (int i=0; ; i++) { m=m+ar[i]; if (m==15) sum++; else if (m>k) } m=0; for (int i=0; ; i--) { m=m+ar[i]; if (m==15) sum++; else if (m>k) } } */ /* #include <stdio.h> int a[100000]={}; void swap(int x, int y) { int t=a[x]; a[x]=a[y]; a[y]=t; } //quick-sort void qs(int s, int e) { int p=s,low=s,high=e+1; if(s>=e) return ; do { do { low++; }while(a[low]<a[p]); do { high--; }while(a[high]>a[p]); //a[low] a[p]보다 큰값 //a[high] a[p]보다 작은값 if(low<high) swap(low,high); }while(low<high); swap(high,p); qs(s,high-1); qs(high+1,e); } #include <stdio.h> int a[100000]={}; void swap(int x, int y) { int t=a[x]; a[x]=a[y]; a[y]=t; } //quick-sort void qs(int s, int e) { int p=s,low=s,high=e+1; if(s>=e) return ; do { do { low++; }while(a[low]<a[p]); //a[low]가 기준값보다 크다. do { high--; }while(a[high]>a[p]); //a[high]가 기준값보다 작다. if(low<high) swap(low,high); //작은값이 오른쪽에 있고, 큰값이 왼쪽에 있으니까 둘이 자리를 바꿔라 }while(low<high); //a[p]룰 기준으로 작은값은 모두 왼쪽에, 큰값은 모두 오른쪽에 배치완료. swap(high,p); //기준값을 가운데로 옮겨놓고 qs(s,high-1);//기준값 왼쪽 정렬해라 qs(high+1,e); //기준값 오른쪽 정렬해라 } int main() { int n,i; scanf("%d",&n); for (i=0; i<n; i++) { scanf("%d",&a[i]); }qs(0,n-1); for (i=0; i<n; i++) { printf("%d\n",a[i]); } } */ #include <stdio.h> int a[50000]={}; 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); } void swap(int x, int y) { int t=a[x]; a[x]=a[y]; a[y]=t; } //quick-sort void qs(int s, int e) { int p=s,low=s,high=e+1; if(s>=e) return ; do { do { low++; }while(a[low]<a[p]); //a[low]가 기준값보다 크다. do { high--; }while(a[high]>a[p]); //a[high]가 기준값보다 작다. if(low<high) swap(low,high); //작은값이 오른쪽에 있고, 큰값이 왼쪽에 있으니까 둘이 자리를 바꿔라 }while(low<high); //a[p]룰 기준으로 작은값은 모두 왼쪽에, 큰값은 모두 오른쪽에 배치완료. swap(high,p); //기준값을 가운데로 옮겨놓고 qs(s,high-1);//기준값 왼쪽 정렬해라 qs(high+1,e); //기준값 오른쪽 정렬해라 } int main() { int n,i,j,tmp; int br[50000]={}; scanf("%d",&n); for (i=0; i<n; i++) { scanf("%d",&a[i]); br[i]=a[i]; } qs(0,n-1); for (i=0; i<n; i++) { printf("%d ",bs(0,n-1,br[i])); } }

/*#include <stdio.h> void f(int* a,int len) { for(int i=0;i<len;i++) { printf("%d ",a[i]); } } void ff(char* s) { printf("%s",s); } int main() { int arr[5]={5,4,3,2,1}; // int* pa=&a; char str[5]; scanf("%s",str); ff(str); //printf("%d\n",a); // printf("%d\n",pa); // printf("%d\n",*pa); // f(arr,5); return 0; }*/ /* #include <stdio.h> void f(char*s,int a,int b) { for (int i=a; i<a+b; i++) { printf("%c",s[i]); } } int main() { int a,b,i,n; char str[101]={}; scanf("%s",str); scanf("%d %d",&a,&b); f(str,a,b); } */ /* #include <stdio.h> int arr[1000000]={}; //binary_search int bs(int s, int e, int k) { int mid=(s+e)/2; if(s>e) return -1; if(arr[mid]==k) return mid; else if(arr[mid]<k) bs(mid+1,e,k); else bs(s,mid-1,k); } int main() { int n,m,i,j,a; scanf("%d",&n); for (i=1; i<=n; i++) { scanf("%d",&arr[i]); } scanf("%d",&m); for (i=1; i<=m; i++) { scanf("%d",&a); printf("%d ",bs(1,n,a)); } } #include <stdio.h> int ar[100000]={}; int n; int bs(int s, int e, int k) { int mid= (s+e)/2; if (s==e) { if(k<=ar[mid]) return mid; else return n+1; } if (k<=ar[mid]) bs (s,mid,k); else bs (mid+1,e,k); } int main() { int k,i; scanf("%d %d",&n,&k); for (i=1; i<=n; i++) { scanf("%d",&ar[i]); } printf("%d",bs(1,n,k)); for (i=0; i<n; i++) { if (k==ar[i]) printf("%d",i+1); if (k>ar[n-1]) printf("%d",n+1); } } */ #include <stdio.h> int ar[50000]={}; int bs(int s, int e, int k) { int mid=(s+e)/2; if(s>e) return -1; if(ar[mid]==k) return mid; else if(ar[mid]<k) bs(mid+1,e,k); else bs(s,mid-1,k); } int main() { int n,i,j,tmp; int br[50000]={}; scanf("%d",&n); for (i=1; i<=n; i++) { scanf("%d",&ar[i]); br[i]=ar[i]; } for(i=1;i<n;i++) { for(j=1;j<=n-i;j++) { if(ar[j]>ar[j+1]) { tmp=ar[j]; ar[j]=ar[j+1]; ar[j+1]=tmp; } } } for (i=1; i<=n; i++) { printf("%d ",bs(1,n,br[i])-1); } }

/*#include <stdio.h> int main() { int i,a,n,sum=0; int memo[24]={}; scanf("%d",&n); for (i=0; i<n; i++) { scanf("%d",&a); memo[a]++; //memo[a] = a라는 숫자가 불린 횟수 } for (i=1; i<=23;i++) { printf("%d ",memo[i]); } }*/ /* #include <stdio.h> int main() { int a,n,i,j,min=100000,max=0; int arr[100001]={}; scanf("%d",&n); for (i=0; i<n; i++) { scanf("%d",&a); arr[a]++; if(min>a) min=a; if(max<a) max=a; } for (i=min; i<=max; i++) { for (j=0; j<arr[i]; j++ ) { printf("%d ",i); } } return 0; } */ /* #include <stdio.h> int map[25][25]={}; int danji[600]={}; //danji[t]= t번째 단지내집수 int b=0,n; void dfs(int i, int j) { if (i>=n || i<0 || j>=n || j<0 || map[i][j]!=1) { return; } b++; map[i][j]=-1; dfs(i,j-1); dfs(i,j+1); dfs(i+1,j); dfs(i-1,j); } int main() { int i,j,cnt=0,tmp=0; scanf("%d",&n); for (i=0; i<n;i++) { for (j=0; j<n; j++) { scanf("%1d",&map[i][j]); } } for(i=0; i<n; i++) { for (j=0; j<n; j++) { if (map[i][j]==1 ) { b=0; cnt++; dfs(i,j); danji[cnt]=b; } } } // for (i=1; i<cnt; i++) { for (j=1; j<=cnt-i; j++) { if (danji[j] > danji[j+1]) { tmp=danji[j]; danji[j]=danji[j+1]; danji[j+1]=tmp; } } } // printf("%d\n",cnt); for(i=1;i<=cnt;i++) { printf("%d\n",danji[i]); } return 0; }*/ /* #include <stdio.h> void f(int* pa, int* pb) { *pa=50; } int main() { int a=30, b=50; printf("%d %d\n",a,b); f(&a,&b); printf("%d %d",a,b); } */ #include <stdio.h> // 이 부분에 들어가야 될 코드를 작성하여 제출 myswap (int*pa, int*pb) { int a; if (*pa>*pb) { a=*pa; *pa=*pb; *pb=a; } } // main() { int a, b; scanf("%d%d", &a, &b); myswap(&a, &b); printf("%d %d", a, b); }

/* #include <stdio.h> int main() { int arr[1001][3]= {}; int i,j,a,n,min; scanf("%d",&n); for (i=1; i<=n; i++) { for(j=0; j<3; j++) { scanf("%d",&arr[i][j]); } } for(i=n-1; i>=1; i--) { for(j=0; j<3; j++) { if(j==0) { arr[i][j]+=arr[i+1][1] < arr[i+1][2] ? arr[i+1][1]:arr[i+1][2]; } else if(j==1) { arr[i][j]+=arr[i+1][0] < arr[i+1][2] ? arr[i+1][0] : arr[i+1][2]; } else { arr[i][j]+=arr[i+1][0] < arr[i+1][1] ? arr[i+1][0]:arr[i+1][1]; } } } min=arr[1][0]<arr[1][1]?arr[1][0]:arr[1][1]; min=min<arr[1][2]?min:arr[1][2]; printf("%d",min); }*/ /* #include <stdio.h> int main() { int a,n,i,j,sum=0; int arr[100001]={}; int memo[100001]={}; scanf("%d",&n); for (i=0; i<n; i++) { scanf("%d",&arr[i]); if(i==0) memo[0]=arr[0]; else memo[i]= memo[i-1]+arr[i]>arr[i]? memo[i-1]+arr[i]:arr[i]; } sum=memo[0]; for (i=0; i<n; i++) { if (sum < memo[i]) sum=memo[i]; } printf("%d",sum); return 0; }*/ /* #include <stdio.h> int main() { int n,i; double a; double arr[10001]={}; double memo[10001]={}; scanf("%d",&n); for (i=0; i<n; i++) { scanf("%lf",&arr[i]); if (i==0) memo[0]=arr[0]; else memo[i]= memo[i-1]>1?memo[i-1]*arr[i]:arr[i]; } a=arr[i]; for (i=0; i<n; i++) { if (a<memo[i]) a=memo[i]; } printf("%.3lf",a); return 0; }*/ #include <stdio.h> int main() { int a,i,sum=0; scanf("%d",&n); }

#include <stdio.h> int main() { int arr[1001][3]= {}; int i,j,a,n,min; scanf("%d",&n); for (i=1; i<=n; i++) { for(j=0; j<3; j++) { scanf("%d",&arr[i][j]); } } for(i=n-1; i>=1; i--) { for(j=0; j<3; j++) { if(j==0) { arr[i][j]+=arr[i+1][1] < arr[i+1][2] ? arr[i+1][1]:arr[i+1][2]; } else if(j==1) { arr[i][j]+=arr[i+1][0] < arr[i+1][2] ? arr[i+1][0] : arr[i+1][2]; } else { arr[i][j]+=arr[i+1][0] < arr[i+1][1] ? arr[i+1][0]:arr[i+1][1]; } } } min=arr[1][0]<arr[1][1]?arr[1][0]:arr[1][1]; min=min<arr[1][2]?min:arr[1][2]; printf("%d",min); }

/*#include <stdio.h> //a>b?a:b //return memo[3]=(st[1]>st[2])?(st[1]+st[3]):(st[2]+st[3]); int memo[301]={}; //memo[k]=k번째 계단까지 왔을 때, 얻을 수 있는 최대점수 int st[301]={}; int rec(int n) { if(memo[n]!=0) return memo[n]; if(n==1) return memo[1]=st[1]; if(n==2) return memo[2]=st[1]+st[2]; if (n==3) return memo[3]=(st[1]>st[2])?(st[1]+st[3]):(st[2]+st[3]); return memo[n]= (st[n-1]+rec(n-3))>(rec(n-2) )?(st[n-1]+rec(n-3)+st[n]):(rec(n-2)+st[n]); /* if(n==3) { if(st[1]>st[2]) { memo[3]=st[3]+st[1]; } else { memo[3]=st[3]+st[2]; } return memo[3]; } if(st[n-1]+rec(n-3)>rec(n-2)) { memo[n]=st[n]+st[n-1]+rec(n-3); } else { memo[n]=st[n]+rec(n-2); } return memo[n]; } int main() { int n,i; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&st[i]); } printf("%d",rec(n)); } /* n st[n] memo[n] 1 10 10 2 20 30 3 15 35 4 25 25 + 25vs 30 55 5 10 10 + 55 vs 35 65 6 20 75 vs 65 */ /* #include <stdio.h> int main() { int a,n,i,m=1; scanf("%d %d",&a, &n); for (i=0; i<n; i++) { m=m*a; } printf("%d",&m); }*/ //red 0 //green 1 //blue 2 #include <stdio.h> int main() { int arr[1001][3]= {}; int i,j,a,n,sum=0,min=10000000; scanf("%d",&n); for (i=0; i<n; i++) { for(j=0; j<3; j++) { scanf("%d",&arr[i][j]); } } for(j=0; j<3; j++) //color { sum=arr[0][j]; //cost a=j; for(i=1; i<n; i++) { if(a==0) //이전에 red를 칠했으면 ? { sum+=arr[i][1] < arr[i][2] ? arr[i][1]:arr[i][2]; a=arr[i][1] < arr[i][2] ? 1:2; } else if(a==1) { sum+=arr[i][0] < arr[i][2] ? arr[i][0] : arr[i][2]; a=arr[i][0] < arr[i][2] ? 0:2; } else { sum+=arr[i][0] < arr[i][1] ? arr[i][0]:arr[i][1]; a=arr[i][0]<arr[i][1] ? 0:1; } } if(min>sum) { min=sum; } } printf("%d",min); }

/* #include <stdio.h> void rec(int n) //26 AAA==703 { if (n==0) return; rec((n-1)/26); printf("%c" ,(n-1)%26+'A'); } int main() { int n,i; scanf("%d",&n); rec(n); } */ /* 1 2 3 A B C */ /*memo[n] : rec(n) : 계단이 n개 있을 때 오를 수 있는 가지수 rec(1) = 1 rec(2) = 2 rec(3) = 4 rec(4) = 7 rec(5) = 13 rec(6) = 24*/ /* #include <stdio.h> int memo[100001]={0,1,2,4,0}; int rec(int n) { if(memo[n]!=0) return memo[n]; if (n==1) return memo[n]=1; if (n==2) return memo[n]=2; if (n==3) return memo[n]=4; return memo[n]=(rec(n-3)+rec(n-2)+rec(n-1))%1000; } int main() { int n; scanf("%d",&n); printf("%d",rec(n)); } */ #include <stdio.h> int memo[301]={}; int st[301]={}; int rec(int n) { if(n==1) return memo[1]=st[1]; if(n==2) return memo[2]=st[1]+st[2]; if(n==3) return memo[3]=st[3]+st[1]; } int main() { int n,i; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",st[i]); } rec(n); }

/* #include <stdio.h> int memo[41]={}; int rec(int n) { if(memo[n]!=0) return memo[n]; if (n==1 || n==2) return memo[n]=1; return memo[n]=rec(n-1)+rec(n-2); } int main() { int n; scanf("%d",&n); printf("%d",rec(n)); } 1916 1930 3702 4564 재귀+메모이제이션 */ /* #include <stdio.h> int memo[201]={}; int rec(int n) { if (memo[n]!=0) return memo[n]; if(n==1 || n==2) return memo[n]=1; return memo[n]=(rec(n-1)+rec(n-2))%10009; } int main() { int n; scanf("%d",&n); printf("%d",rec(n)); }*/ /* #include <stdio.h> int memo[15][15]= {}; int rec(int k, int n) { if(memo[k][n]!=0) return memo[k][n]; if(k==0) return memo[k][n]=n; if(n==0) return memo[k][n]=0; return memo[k][n]=rec(k,n-1)+rec(k-1,n); } int main() { int k,n; while( scanf("%d %d", &k, &n) != EOF ) printf("%d\n", rec(k, n)); } */ /* #include <stdio.h> int memo[51][51]={}; int rec(int r, int c) { if (memo[r][c]!=0) return memo[r][c]; if (r<=1 || c<=1) return memo[r][c]=1; return memo[r][c]=(rec(r-1,c)+rec(r,c-1))%100000000; } int main() { int r,c; scanf("%d %d",&r,&c); printf("%d",rec(r,c)); } */ /* #include <stdio.h> int rec() { } int main() { int n,i; scanf("%d",&n); } */ /* #include <stdio.h> int rec(int n) { } int main() { int n,i; scanf("%d",&n); }*/ #include <stdio.h> int main() { int n,i,j; int arr[1001][3]={}; scanf("%d",&n); for (i=0;i<n;i++) { for(j=0;j<3;j++) { scanf("%d",&arr[i][j]); } } }

/*#include <stdio.h> int main() { int n,i,j,tmp; int arr[4500000]={}; scanf("%d",&n); for (i=0; i<n; i++) { scanf("%d",&arr[i]); } for (j=0; j<n;j++) { for(i=0; i<n; i++) { if(arr[i]>arr[i+1]) { tmp=arr[i+1]; arr[i+1]=arr[i]; arr[i]=tmp; } } } for (i=0; i<n; i++) { printf("%d ",arr[i]); } } #include <stdio.h> int main () { int arr[4500000]; int n,i,j; scanf("%d",&n); for (i=0; i<n; i++) { scanf("%d",arr[i]); } } */ /* #include <stdio.h> int main () { int a,x,y,p,q; scanf("%d",&a); x=a%10+6; y=a%12+8; if (x>10) x=x-10; if (y>12) y=y-12; printf("%c%d",y+'A',x); }*/ /* #include <stdio.h> int main() { int a=0,b=1000,n,i; int arr[1000]={}; scanf("%d",&n); for (i=0;i<n;i++) { scanf("%d",&arr[i]); } for (i=0;i<n;i++) { if (arr[i]>a) a=arr[i]; if (arr[i]<b) b=arr[i]; } printf("%d",a-b); }*/ /* #include <stdio.h> int main() { int a,b,c,n,sum; scanf("%d %d %d",&a,&b,&c); scanf("%d",&n); sum=(n+c)%3600; a=a+sum; n=n-3600*sum; sum=n%60; b=b+sum; n=n-60*sum; c=c+n; if (c>59) { c=60-c; b++; } if (b>59) { b=60-b; a++; } if (a>23) { a=24-a; } printf("%d %d %d",a,b,c); }*/ /* #include <stdio.h> int main() { int a,b,c,d,sum; scanf("%d %d %d %d",&a,&b,&c,&d); c=c+d; sum=c/60; c=c%60; b=b+sum; sum=b/60; b=b%60; a=a+sum; a=a%24; printf("%d %d %d",a,b,c); }*/ #include <stdio.h> rec(int n) { 'A'+1; if(n==0) return; rec(n-1); } int main() { int n,i,j; scanf("%d",&n); }

/*#include <stdio.h> char map[10][10]={}; void dfs(int a, int b) { if (a<0 || b<0 || a>9 || b>9 || map[a][b]=='*') return; map[a][b]='*'; dfs(a-1,b); dfs(a+1,b); dfs(a,b+1); dfs(a,b-1); } int main() { int a,b,i,j; char tmp; for (i=0; i<10; i++) { for (j=0; j<10; j++) { scanf("%c",&map[i][j]); } scanf("%c",&tmp); } scanf("%d %d", &a, &b); dfs(b,a); for (i=0; i<10; i++) { for (j=0; j<10; j++) { printf("%c",map[i][j]); } printf("\n"); } } /* _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ * * * * _ _ _ _ _ _ * _ _ * _ _ _ * * * * * * * _ _ _ * _ _ * _ * * _ _ _ * _ _ * * * * _ __*____*__ __*____*__ __******__ __________ */ /* #include <stdio.h> #define SIZE 1001 int map[SIZE][SIZE]={}; int n,m,day=0; typedef struct { int x, y; }point; point queue[SIZE]; int front=-1,rear=-1; void enq(point p) { map[p.x][p.y]=1; rear++; queue[rear]=p; } point deq() { if(front!=rear) { front++; return queue[front]; } } void bfs(point p) //P의 사방에 있는 점 중에 이동할 수 있는 점이 있으면 그 점을 enq해라 { point tmp; if (p.x+1>=1&& p.x+1<=n && p.y<=m && p.y>=1 && map[p.x+1][p.y]==0) { tmp.x=p.x+1; tmp.y=p.y; enq(tmp); } if (p.x-1>=1&& p.x-1<=n && p.y<=m && p.y>=1 && map[p.x-1][p.y]==0) { tmp.x=p.x-1; tmp.y=p.y; enq(tmp); } if (p.x>=1&& p.x<=n && p.y+1<=m && p.y+1>=1 && map[p.x][p.y+1]==0) { tmp.x=p.x; tmp.y=p.y+1; enq(tmp); } if (p.x>=1&& p.x<=n && p.y-1<=m && p.y-1>=1 && map[p.x][p.y-1]==0) { tmp.x=p.x; tmp.y=p.y-1; enq(tmp); } } int main() { int i,j; point p; scanf("%d %d",&m, &n); for (i=1; i<=n; i++) { for (j=1; j<=m; j++) { scanf("%d",&map[i][j]); if(map[i][j]==1) { p.x=i; p.y=j; enq(p); } } } while(rear!=front) { p=deq(); bfs(p); } printf("%d",day); return 0; } */ /* 0 1 2 3 4 5 6 7 8 i 0 0 1 0 1 0 2 0 1 arr[i] #include <stdio.h> int main() { int n,i,j,tmp; int arr[4500001]= {}; scanf("%d",&n); for (i=0; i<n; i++) { scanf("%d",arr[i]); } for(j=0; j<n; j++) { for (i=0; i<n; i++) { if (arr[i]>arr[i+1]) { tmp=arr[i+1]; arr[i+1]=arr[i]; arr[i]=tmp; } } } for (i=0;i<n;i++) { printf("%d ",arr[i]); } } */ /* #include <stdio.h> int main() { int score[24]={}; int n,i,t; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&t); score[t]++; } for (i=1; i<=23; i++) { printf("%d ",score[i]); } return 0; } memoization 메모이제이션 arr[i]=i번째 들어온 데이터 arr[i]=i에 관련된 정보 ex) i가 몇번 입력되었는지? i가 입력된 적이 있는지? 1430 1412 */ /* #include <stdio.h> int main() { int arr[26]={}; int i,j,n; char str[91]; gets(str); for (i=0;i<strlen(str);i++) { if(str[i]>='a' && str[i]<='z') { arr[str[i]-'a']++; } } for (i=0; i<26;i++) { printf("%c:%d\n",i+'a',arr[i]); } return 0; }*/ #include <stdio.h> int main() { int arr[10000001]={}; int n,m,i,b,j; scanf("%d",&n); for (i=0; i<n; i++) { scanf("%d",&b); arr[b]=1; } scanf("%d",&m); for (i=0;i<m;i++) { scanf("%d",&b); printf("%d ",arr[b]); } return 0; } /* ///0 0 1 2 1 1 2 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 ///0 0 1 2 1 1 2 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 ///0 0 0 0 0 0 0 0 0 0 0 0 0 ///0 0 0 0 0 0 0 0 0 0 0 0 0 0 ///0 1 2 1 1 2 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 ///1 2 1 1 2 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ///1 2 1 1 2 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0*/

/*#include <stdio.h> char map[10][10]={}; void dfs(int a, int b) { if (a<0 || b<0 || a>9 || b>9 || map[a][b]=='*') return; map[a][b]='*'; dfs(a-1,b); dfs(a+1,b); dfs(a,b+1); dfs(a,b-1); } int main() { int a,b,i,j; char tmp; for (i=0; i<10; i++) { for (j=0; j<10; j++) { scanf("%c",&map[i][j]); } scanf("%c",&tmp); } scanf("%d %d", &a, &b); dfs(b,a); for (i=0; i<10; i++) { for (j=0; j<10; j++) { printf("%c",map[i][j]); } printf("\n"); } } /* _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ * * * * _ _ _ _ _ _ * _ _ * _ _ _ * * * * * * * _ _ _ * _ _ * _ * * _ _ _ * _ _ * * * * _ __*____*__ __*____*__ __******__ __________ */ /* #include <stdio.h> #define SIZE 1001 int map[SIZE][SIZE]={}; int n,m,day=0; typedef struct { int x, y; }point; point queue[SIZE]; int front=-1,rear=-1; void enq(point p) { map[p.x][p.y]=1; rear++; queue[rear]=p; } point deq() { if(front!=rear) { front++; return queue[front]; } } void bfs(point p) //P의 사방에 있는 점 중에 이동할 수 있는 점이 있으면 그 점을 enq해라 { point tmp; if (p.x+1>=1&& p.x+1<=n && p.y<=m && p.y>=1 && map[p.x+1][p.y]==0) { tmp.x=p.x+1; tmp.y=p.y; enq(tmp); } if (p.x-1>=1&& p.x-1<=n && p.y<=m && p.y>=1 && map[p.x-1][p.y]==0) { tmp.x=p.x-1; tmp.y=p.y; enq(tmp); } if (p.x>=1&& p.x<=n && p.y+1<=m && p.y+1>=1 && map[p.x][p.y+1]==0) { tmp.x=p.x; tmp.y=p.y+1; enq(tmp); } if (p.x>=1&& p.x<=n && p.y-1<=m && p.y-1>=1 && map[p.x][p.y-1]==0) { tmp.x=p.x; tmp.y=p.y-1; enq(tmp); } } int main() { int i,j; point p; scanf("%d %d",&m, &n); for (i=1; i<=n; i++) { for (j=1; j<=m; j++) { scanf("%d",&map[i][j]); if(map[i][j]==1) { p.x=i; p.y=j; enq(p); } } } while(rear!=front) { p=deq(); bfs(p); } printf("%d",day); return 0; } */ /* 0 1 2 3 4 5 6 7 8 i 0 0 1 0 1 0 2 0 1 arr[i] #include <stdio.h> int main() { int n,i,j,tmp; int arr[4500001]= {}; scanf("%d",&n); for (i=0; i<n; i++) { scanf("%d",arr[i]); } for(j=0; j<n; j++) { for (i=0; i<n; i++) { if (arr[i]>arr[i+1]) { tmp=arr[i+1]; arr[i+1]=arr[i]; arr[i]=tmp; } } } for (i=0;i<n;i++) { printf("%d ",arr[i]); } } */ /* #include <stdio.h> int main() { int score[24]={}; int n,i,t; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&t); score[t]++; } for (i=1; i<=23; i++) { printf("%d ",score[i]); } return 0; } memoization 메모이제이션 arr[i]=i번째 들어온 데이터 arr[i]=i에 관련된 정보 ex) i가 몇번 입력되었는지? i가 입력된 적이 있는지? 1430 1412 */ /* #include <stdio.h> int main() { int arr[26]={}; int i,j,n; char str[91]; gets(str); for (i=0;i<strlen(str);i++) { if(str[i]>='a' && str[i]<='z') { arr[str[i]-'a']++; } } for (i=0; i<26;i++) { printf("%c:%d\n",i+'a',arr[i]); } return 0; }*/ #include <stdio.h> int main() { int arr[10000001]={}; int n,m,i,b,j; scanf("%d",&n); for (i=0; i<n; i++) { scanf("%d",&b); arr[b]=1; } scanf("%d",&m); for (i=0;i<m;i++) { scanf("%d",&b); printf("%d ",arr[b]); } return 0; } /* ///0 0 1 2 1 1 2 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 ///0 0 1 2 1 1 2 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 ///0 0 0 0 0 0 0 0 0 0 0 0 0 ///0 0 0 0 0 0 0 0 0 0 0 0 0 0 ///0 1 2 1 1 2 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 ///1 2 1 1 2 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ///1 2 1 1 2 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0*/

/*#include <stdio.h> char map[10][10]={}; void dfs(int a, int b) { if (a<0 || b<0 || a>9 || b>9 || map[a][b]=='*') return; map[a][b]='*'; dfs(a-1,b); dfs(a+1,b); dfs(a,b+1); dfs(a,b-1); } int main() { int a,b,i,j; char tmp; for (i=0; i<10; i++) { for (j=0; j<10; j++) { scanf("%c",&map[i][j]); } scanf("%c",&tmp); } scanf("%d %d", &a, &b); dfs(b,a); for (i=0; i<10; i++) { for (j=0; j<10; j++) { printf("%c",map[i][j]); } printf("\n"); } } /* _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ * * * * _ _ _ _ _ _ * _ _ * _ _ _ * * * * * * * _ _ _ * _ _ * _ * * _ _ _ * _ _ * * * * _ __*____*__ __*____*__ __******__ __________ */ #include <stdio.h> #define SIZE 1001 int map[SIZE][SIZE]={}; int n,m,day=0; typedef struct { int x, y; }point; point queue[SIZE]; int front=-1,rear=-1; void enq(point p) { map[p.x][p.y]=1; rear++; queue[rear]=p; } point deq() { if(front!=rear) { front++; return queue[front]; } } void bfs(point p) //P의 사방에 있는 점 중에 이동할 수 있는 점이 있으면 그 점을 enq해라 { point tmp; if (p.x+1>=1&& p.x+1<=n && p.y<=m && p.y>=1 && map[p.x+1][p.y]==0) { tmp.x=p.x+1; tmp.y=p.y; enq(tmp); } if (p.x-1>=1&& p.x-1<=n && p.y<=m && p.y>=1 && map[p.x-1][p.y]==0) { tmp.x=p.x-1; tmp.y=p.y; enq(tmp); } if (p.x>=1&& p.x<=n && p.y+1<=m && p.y+1>=1 && map[p.x][p.y+1]==0) { tmp.x=p.x; tmp.y=p.y+1; enq(tmp); } if (p.x>=1&& p.x<=n && p.y-1<=m && p.y-1>=1 && map[p.x][p.y-1]==0) { tmp.x=p.x; tmp.y=p.y-1; enq(tmp); } } int main() { int i,j; point p; scanf("%d %d",&m, &n); for (i=1; i<=n; i++) { for (j=1; j<=m; j++) { scanf("%d",&map[i][j]); if(map[i][j]==1) { p.x=i; p.y=j; enq(p); } } } while(rear!=front) { p=deq(); bfs(p); } printf("%d",day); return 0; }

/*#include <stdio.h> int n; int map[100][100]= {},map1[100][100]={}; void dfs(int i, int j,int h) { if (i>=n || i<0 || j>=n || j<0 || map[i][j]<=h) return ; map[i][j]=-1; dfs (i+1,j,h); dfs (i-1,j,h); dfs (i,j+1,h); dfs (i,j-1,h); } void copymap() { for (int i=0; i<n; i++) { for (int j=0; j<n; j++) { map[i][j]=map1[i][j]; } } } int main() { int i,j,max=1; int minh=100,maxh=1,num; scanf("%d",&n); for (i=0; i<n; i++) { for (j=0; j<n; j++) { scanf("%d",&map[i][j]); map1[i][j]=map[i][j]; if(maxh<map[i][j]) maxh=map[i][j]; if(minh>map[i][j]) minh=map[i][j]; } } for(int h=minh; h<maxh; h++) { copymap(); num=0; for (i=0; i<n; i++) { for (j=0; j<n; j++) { if(map[i][j]>h) { dfs(i,j,h); num++; } } } if(max<num) { max=num; } //printf("h = %d num=%d max = %d\n",h,num,max); } printf("%d",max); return 0; } */ #include <stdio.h> int map[11][11]={}, map1[11][11]={}; void dfs(int i, int j) { if (i>9 || i<=0 || j>9 || j<=0 || map1[i][j]!=0) return; map1[i][j]=-1; dfs(i,j+1); dfs(i,j-1); dfs(i+1,j); dfs(i-1,j); } /*void bomb(int i, int j) { if (i>=9 || i<0 || j>=9 || j<0 || map[i][j]!=0) return; if (map[i][j]) bomb(i+1,j); bomb(i-1,j); bomb(i,j+1); bomb(i,j-1); bomb(i+1,j+1); bomb(i+1,j-1); bomb(i-1,j+1); bomb(i-1,j-1); }*/ int main() { int i,j,r,c; for (i=1; i<=9; i++) { for (j=1; j<=9; j++) { scanf("%d",&map[i][j]); } } scanf("%d %d",&r,&c); for (i=1; i<=9; i++) { for (j=1; j<=9; j++) { map1[i][j]=map[i+1][j]+map[i-1][j]+map[i][j+1]+ map[i][j-1]+map[i+1][j+1]+map[i+1][j-1]+ map[i-1][j+1]+map[i-1][j-1]; } } dfs(r,c); for (i=1; i<=9; i++) { for (j=1; j<=9; j++) { printf("%2d ",map1[i][j]); } printf("\n"); } return 0; }

/* //단지 수 세기 dfs 재귀 #include <stdio.h> int map[25][25]= {},n,m=0; int ar[] void dfs(int i, int j) { if(i>=n || i<0 || j>=n || j<0 ||map[i][j]!=1) return ; map[i][j]=-1; //visited check dfs(i-1,j); dfs(i+1,j); dfs(i,j-1); dfs(i,j+1); } void view() { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { printf("%2d ",map[i][j]); } printf("\n"); } printf("\n"); } int main() { int i, j,cnt=0; scanf("%d",&n); for (i=0; i<n; i++) { for (j=0; j<n; j++) { scanf("%1d",&map[i][j]); } } for (i=0; i<n; i++) { for (j=0; j<n; j++) { if (map[i][j]==1) { // m=0; dfs(i,j); // printf("%d ",m); cnt++; // view(); } } } printf("%d\n",cnt); } */ /* #include <stdio.h> int map[25][25]={}; int danji[600]={}; //danji[t]= t번째 단지내집수 int b=0,n; void dfs(int i, int j) { if (i>=n || i<0 || j>=n || j<0 || map[i][j]!=1) { return; } b++; map[i][j]=-1; dfs(i,j-1); dfs(i,j+1); dfs(i+1,j); dfs(i-1,j); } int main() { int i,j,cnt=0,tmp=0; scanf("%d",&n); for (i=0; i<n;i++) { for (j=0; j<n; j++) { scanf("%1d",&map[i][j]); } } for(i=0; i<n; i++) { for (j=0; j<n; j++) { if (map[i][j]==1 ) { b=0; cnt++; dfs(i,j); danji[cnt]=b; } } } // for (i=1; i<cnt; i++) { for (j=1; j<=cnt-i; j++) { if (danji[j] > danji[j+1]) { tmp=danji[j]; danji[j]=danji[j+1]; danji[j+1]=tmp; } } } // printf("%d\n",cnt); for(i=1;i<=cnt;i++) { printf("%d\n",danji[i]); } return 0; } */ #include <stdio.h> int map[101][101]= {}; int m,n,cnt=0,d=0; int danji[5000]={}; void dfs(int i, int j) { if (i>=m|| i<0 || j>=n || j<0 || map[i][j]!=0) return; d++; map[i][j]=-1; dfs(i,j+1); dfs(i,j-1); dfs(i+1,j); dfs(i-1,j); } int main() { int t,k,i,j,x,y,a,b,tmp=0; scanf("%d %d %d",&m,&n,&k); for(t=0; t<k; t++) { scanf("%d %d %d %d",&a,&b,&x,&y); for(i=b;i<y;i++) { for(j=a;j<x;j++) { map[i][j]=1; } } } for(i=0;i<m;i++) { for(j=0;j<n;j++) { if(map[i][j]==0) { d=0; cnt++; dfs(i,j); danji[cnt]=d; } } } for (i=1; i<cnt;i++) { for (j=1;j<=cnt-i;j++) { if (danji[j] > danji[j+1]) { tmp=danji[j+1]; danji[j+1]=danji[j]; danji[j]=tmp; } } } printf("%d\n",cnt); for (i=1; i<=cnt; i++) { printf("%d ",danji[i]); } // /* for(i=0;i<m;i++) { for(j=0;j<n;j++) { printf("%d ",map[i][j]); } printf("\n"); }*/ }

/* #include <stdio.h> #define SIZE 200 int stack[SIZE]; int top=-1; push(int data) { stack[++top]=data; } int pop() { if(top!=-1) { return stack[top--]; } return 0; } int main() { char str1[100]= {}; char str2[100]= {},tmp[100]; int a,b,i,n,c=0,num=0; scanf("%s %s",str1, str2); a=strlen(str1)-1; b=strlen(str2)-1; if(a<b) { strcpy(tmp,str1); strcpy(str1,str2); strcpy(str2,tmp); a=strlen(str1)-1; b=strlen(str2)-1; } while(b>=0) { num=str1[a]-'0'+str2[b]-'0'+c; c=num/10; //printf("%d",num%10); push(num%10); a--; b--; } while(a>=0) { num=str1[a]-'0'+c; c=num/10; //printf("%d",num%10); push(num%10); a--; } if(c==1) push(1); while(top!=-1) { printf("%d",pop()); } return 0; } */ //단지 수 세기 dfs 재귀 #include <stdio.h> int map[25][25]= {},n,m=0; int ar[] void dfs(int i, int j) { if(i>=n || i<0 || j>=n || j<0 ||map[i][j]!=1) return ; map[i][j]=-1; //visited check dfs(i-1,j); dfs(i+1,j); dfs(i,j-1); dfs(i,j+1); } /*void view() { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { printf("%2d ",map[i][j]); } printf("\n"); } printf("\n"); }*/ int main() { int i, j,cnt=0; scanf("%d",&n); for (i=0; i<n; i++) { for (j=0; j<n; j++) { scanf("%1d",&map[i][j]); } } for (i=0; i<n; i++) { for (j=0; j<n; j++) { if (map[i][j]==1) { // m=0; dfs(i,j); // printf("%d ",m); cnt++; // view(); } } } printf("%d\n",cnt); } /* #include <stdio.h> char map[100][100]; int c=0,a,b; dfs(int i, int j) { if (i<0 || i>=a || j<0 || j>=b || map[i][j]!='L') return ; map[i][j]=','; dfs(i-1,j); dfs(i+1,j); dfs(i,j+1); 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 i,j,cnt=0; scanf("%d %d",&b,&a); for (i=0; i<a; i++) { for (j=0; j<b; j++) { scanf(" %c",&map[i][j]); } } for (i=0; i<a; i++) { for (j=0;j<b;j++) { if (map[i][j]=='L') { dfs(i,j); c++; } } } printf("%d",c); return 0; } */ /* #include <stdio.h> int map[7][7]={},m; void dfs(int i, int j,int color) { if ( i<0 || j<0 || j>=7 || i>=7 ||map[i][j]!=color) return ; map[i][j]=-1; m++; dfs(i-1,j,color); dfs(i+1,j,color); dfs(i,j+1,color); dfs(i,j-1,color); } int main() { int a,i,j,cnt=0; for (i=0; i<7; i++) { for (j=0; j<7; j++) { scanf("%d",&map[i][j]); } } for (i=0; i<7; i++) { for (j=0; j<7; j++) { m=0; if(map[i][j]!=-1) dfs(i,j,map[i][j]); if(m>=3) { cnt++; } } } printf("%d",cnt); return 0; } */

/* #include <stdio.h> int main() { int i,j,k,n,a,b=-2,x,y; int player[2][9]= {}; int ar[11][11]= {},arr[11][11]={}; for (i=1; i<=10; i++) { for (j=1; j<=10; j++) { scanf("%d",&ar[i][j]); arr[i][j]=ar[i][j]; } } for (i=1; i<=10; i++) { for (j=1; j<=10; j++) { if (ar[i][j]>0) { a=ar[i][j]; arr[i][j]=b; for (k=i+1; k<=i+a; k++) { if (k>10 || ar[k][j]==-1) break; arr[k][j]=b; } for (k=i-1; k>=i-a; k--) { if (k<1 || ar[k][j]==-1) break; arr[k][j]=b; } for (k=j+1; k<=j+a; k++) { if (k>10 || ar[i][k]==-1) break; arr[i][k]=b; } for (k=j-1; k>=j-a; k--) { if (k<1 || ar[i][k]==-1) break; arr[i][k]=b; } } } } scanf("%d",&n); for (j=1; j<=n; j++) { scanf("%d %d", &player[0][j], &player[1][j]); if (arr[player[0][j]][player[1][j]]==0) { arr[player[0][j]][player[1][j]]=j; } } for (i=1; i<=10; i++) { for (j=1; j<=10; j++) { printf("%d ",arr[i][j]); } printf("\n"); } printf("Character Information\n"); for (j=1; j<=n; j++) { if (arr[player[0][j]][player[1][j]]==j) { printf("player %d survive\n",j); } else { printf("player %d dead\n",j); } } return 0; }*/ /* #include <stdio.h> int main() { char str[100000]={}; int a,i; for (i=0; ;i++) { scanf("%s",str); } for (i=0;i<strlen(str) ;i++) { a=i; } for (i=0; i<a; i++) { if (str[i]=='(') { if (str[i+1]=='(') { } } } }*/ #include <stdio.h> #define SIZE 200 int stack[SIZE]; int top=-1; push(int data) { stack[++top]=data; } int pop() { if(top!=-1) { return stack[top--]; } return 0; } int main() { char str1[100]= {}; char str2[100]= {}; int a,b,i,n,c=0,num=0; scanf("%s %s",str1, str2); a=strlen(str1)-1; b=strlen(str2)-1; while(b>=0) { num=str1[a]-'0'+str2[b]-'0'+c; c=num/10; //printf("%d",num%10); push(num%10); a--; b--; } while(a>=0) { num=str1[a]-'0'+c; c=num/10; //printf("%d",num%10); push(num%10); a--; } if(c==1) push(1); while(top!=-1) { printf("%d",pop()); } return 0; }

#include <stdio.h> int main() { int i,j,k,n,a,b=-2,x,y; int ar[10][10]= {}; for (i=1; i<=10; i++) { for (j=1; j<=10; j++) { scanf("%d",&ar[i][j]); } } for (i=1; i<=10; i++) { for (j=1;j<=10;j++) { if (ar[i][j]>0) { // a=ar[i][j]; for (k=i+1; k<=i+a; k++) { if (ar[k][j]==-1) break; ar[k][j]=b; ar[i][j]=-2; } for (k=i-1; k<=i-a; k--) { if (ar[k][j]==-1) break; ar[k][j]=b; } for (k=j+1;k<=j+a;k++) { ar[i][j]=b; if (ar[k][j]==-1) break; ar[k][j]=b; } for (k=j-1; k<=j-a; k--) { if (ar[k][j]==-1) break; ar[k][j]=b; } } } } for (i=1;i<=10;i++) { printf("\n"); for (j=1;j<=10;j++) { printf("%d ",ar[i][j]); } } printf("Character Information"); scanf("%d",&n); for (i=1; i<n; i++) { scanf("%d %d", &x, &y); if (ar[x][y]==0) { printf("player %d survive",i); } } }

/* #include <stdio.h> typedef struct { int score; int math; int information; } st; int main() { int n,i,j; st ar[1001],tmp; scanf("%d",&n); for (i=1; i<=n; i++) { scanf("%d %d",&ar[i].math, &ar[i].information); ar[i].score=i; } for (i=1; i<n; i++) { for(j=1; j<=n-i; j++) { if (ar[j].math < ar[j+1].math) { tmp=ar[j]; ar[j]=ar[j+1]; ar[j+1]=tmp; } else if(ar[j].math == ar[j+1].math) { if(ar[j].information < ar[j+1].information) { tmp=ar[j]; ar[j]=ar[j+1]; ar[j+1]=tmp; } else if(ar[j].information== ar[j+1].information) { if(ar[j].score > ar[j+1].score) { tmp=ar[j]; ar[j]=ar[j+1]; ar[j+1]=tmp; } } } } } for (i=1; i<=n; i++) { printf("%d %d %d\n",ar[i].score,ar[i].math, ar[i].information); } return 0; }*/ /* #include <stdio.h> int main() { int i,j,a=300,b=60,c=10,t,x=0,y=0,z=0; scanf("%d",&t); for ( i=1; ; i++) { if (t<a) break; t=t-a; x=i; } for (i=1; ; i++) { if (t<b) break; t=t-b; y=i; } for (i=1; i<7; i++) { if (t==0) break; t=t-c; z++; } if (t!=0) { printf("-1"); } else { printf("%d %d %d ",x,y,z); } }*/ /* #include <stdio.h> int main() { int i,j,a=1,n; scanf("%d",&n); for (i=0; i<n; i++) { for (j=0; j<n; j++) } }*/ #include <stdio.h> int main() { int i,j,k,n,a,b,x,y; int ar[10][10]= {}; for (i=1; i<=10; i++) { for (j=1; j<=10; j++) { scanf("%d",&arr[i][j]); } } for (i=1; i<=10; i++) { for (j=1;j<=10;j++) { if (ar[i][j]>0) { a=ar[i][j]; for (k=i+1; k<=i+a; k++) { if (ar[k][j]==-1) break; ar[i][j]=-2; } } } } scanf("%d",&n); for (i=1; i<n; i++) { scanf("%d %d", &x, &y); } }

#include <stdio.h> typedef struct { int math; int information; }student; int main() { int n,i,a=1,b=0,sum=0; student ar[1001]; scanf("%d",&n); for (i=1; i<=n; i++) { scanf("%d &d",ar[i].math, &ar[i].information); } for (i=1; i<=n; i++) { if (ar[i].math >= sum) { sum=ar[i].math; b=i; } } }

/*#include <stdio.h> #define SIZE 201 int stack[SIZE]; int top=-1; //data가 마지막으로 저장된 위치 void push(int data) { if(top==SIZE-1) return ; top++; stack[top]=data; } int pop() { if(top==-1) return 0; return stack[top--]; } void topp() { if(top==-1) printf("-1\n"); else printf("%d\n",stack[top]); } void size() { printf("%d\n",top+1); } void empty() { if (top==-1) printf("true\n"); else printf("false\n"); } int main() { int n,i,j,a,num=0; char str[50]; scanf("%d\n",&n); for(i=0;i<n;i++) { gets(str); if(str[1]=='u') //push { for(j=6;;j++) { num=num*10+str[j]-'0'; if(str[j+1]==' ') { push(num); num=0; break; } } } else if(str[0]=='p') //pop { pop(); } else if(str[0]=='t')//top { topp(); } else if (str[0]=='s')//size { size(); } else if (str[0]=='e')//empty { empty(); } } }*/ #include <stdio.h> #define SIZE 201 int stack[SIZE]; int top=-1; void push(int data) { if(top==SIZE-1) return ; top++; stack[top]=data; } int pop() { if(top==-1) return 0; return stack[top--]; } int main() { int a,b,n,i,j,num=0; char str[201]; gets(str); n=strlen(str); for(i=0;i<n;i++) { if('0'<=str[i] && str[i]<='9') { num=num*10+str[i]-'0'; if(str[i+1]==' ') { push(num); num=0; } } else if(str[i]=='+') { a=pop(); b=pop(); push(a+b); } else if(str[i]=='*') { a=pop(); b=pop(); push (a*b); } else if(str[i]=='-') { a=pop(); b=pop(); push (b-a); } } printf("%d",pop()); return 0; }