https://www.acmicpc.net/problem/11562 플로이드를 돌려서 어찌어찌 해야할 것 같다. 약간의 트릭을 주면 된다. u,v,b를 받아서 양방향 간선이면 d[u][v]=d[v][u]=0, 단방향 간선이면 d[u][v]=0,d[v][u]=1로 줘서 양방향 간선으로 만들어 준다. 그리고 플로이드를 돌리면 모든 정점 사이에 대해서 최소 몇 개의 일방통행인 길을 양방향 통행으로 바꿔야 하는지 알 수 있다. 123456789101112131415161718#include #include #define INF 987654321using namespace std; int n,m,u,v,b,k,s,e,i,j,d[300][300]; int main(){ scanf("%d %d",&n,&m); for..
https://www.acmicpc.net/problem/2458 먼저 플로이드를 돌려서 모든 정점 사이의 거리를 구한다. 그리고 정점 i에서 다른 정점 j에 대해서 하나라도 d[i][j], d[j][i] 모두 알 수 없다면 자신의 키 순서를 정확히 알 수 없다. 12345678910111213141516171819202122232425262728#include #define INF 987654321 int n,m,a,b,i,j,k,ans,d[501][501]; int main(){ scanf("%d %d",&n,&m); for(i=1;i
https://www.acmicpc.net/problem/15683 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586#include #include #include using namespace std; int n,m,cnt,ans=100,map[8][8],tmap[8][8];int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; // 북동남서vector v;int size,p[8]; void go(int x,int y,int d){ while(true..
https://www.acmicpc.net/problem/3474 N!의 오른쪽 끝에 있는 0의 개수를 구하는 문제이다. 0이 만들어지려면 10이 필요하고 이는 소인수 중에서 2와 5의 개수를 세주면 된다. 5가 더 적게 나타나므로 5의 개수만 세주면 된다. 1234567891011121314151617#include int t,n,ans; int main(){ scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=5;i
https://www.acmicpc.net/problem/3176 parent[i][j] = 노드 i의 2^j번째 조상maxd[i][j] = 노드 i부터 2^j번째 조상까지의 간선 중 최대값mind[i][j] = 노드 i부터 2^j번째 조상까지의 간선 중 최소값 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#include #include #include #define N 100005#define INF 987654321using namespace std; int n,m,u,v,w,m..
https://www.acmicpc.net/problem/11438 parent[i][j] = i번 노드의 2^j번째 조상이라고 정의하자. 먼저 DFS를 이용하여 모든 노드의 깊이와 parent[i][0]를 구하자. 그러면 나머지 parent 테이블을 채울 수 있다. j가 20까지인 이유는 2^20 = 1048576 > 100만이기 때문이다. 이렇게 전처리를 하고나면 두 노드의 LCA를 2^k 단위로 건너뛰면서 구할 수 있다. 깊이가 더 큰 노드를 올려서 맞춰준 후 동시에 올리면서 LCA를 찾는다. 결론적으로 DP 테이블을 이용해서 기존의 방법으로는 O(N)이 걸리는 것을 O(logN)만에 해결할 수 있다. 123456789101112131415161718192021222324252627282930313..
https://www.acmicpc.net/problem/1991 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include int tree[26][2]; void preorder(int x) { if(x==-1) return; printf("%c",x+'A'); preorder(tree[x][0]); preorder(tree[x][1]); } void inorder(int x) { if(x==-1) return; inorder(tree[x][0]); printf("%c",x+'A'); inorder(t..
https://www.acmicpc.net/problem/6996 두 단어의 알파벳 구성이 같은지 확인한다. 1234567891011121314151617181920212223#include #include int n,c[26],d[26],p,q,f;char a[101],b[101]; int main(){ scanf("%d",&n); while(n--) { scanf("%s %s",a,b); p=strlen(a),q=strlen(b); for(int i=0;i