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.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD 가능한 간선을 모두 저장한 후 MST를 만든다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #include typedef long long ll;using namespace std; struct Edge{ ll start,end,cost; bool operator
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.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc 먼저 모든 칸의 주변 8방향의 지뢰의 갯수를 표시한다. 그리고 0인 칸을 따로 담는다. BFS로 0이 포함된 영역과 가장자리 숫자까지를 하나로 세준다. 마지막으로 남은 숫자들을 더해주면 최소 횟수가 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include #include #include using namespace std; int t,n,..
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://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWO6cgzKOIEDFAWw&categoryId=AWO6cgzKOIEDFAWw&categoryType=CODE 숫자 4를 사용하지 못하므로 기존의 10진법에서 4를 하나 뺀 9진법으로 생각하자. 4 이상의 숫자들을 하나씩 줄여준 다음 10진법으로 바꾼다. 0층이 없으므로 부호에 따라 계산에 유의하자. 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 #include typedef long long ll; ll cvt(char *a,ll ..