https://www.acmicpc.net/problem/2660 회원의 점수는 나머지 회원들까지 최단 거리의 최대값이다. 이 때 회원의 수가 최대 50명이므로 플로이드로 간편하게 구할 수 있다. 12345678910111213141516171819202122232425262728293031323334#include #include #include using namespace std; int n,i,j,k,d[51][51],p[51],minv=100; int main(){ scanf("%d",&n); for(i=1;i
https://www.acmicpc.net/problem/10159 모든 정점에 대하여 플로이드를 돌리고 비교 관계를 확인한다. 두 정점에 대하여 앞쪽이 더 큰지, 뒤쪽이 더 큰지 둘다 알 수 없다면 비교 관계를 알 수 없다. 123456789101112131415161718#include int n,m,i,j,k,d[101][101]; int main(){ scanf("%d %d",&n,&m); while(m--) scanf("%d %d",&i,&j),d[i][j]|=1; for(k=1;k
https://www.acmicpc.net/problem/2702 유클리드 호제법(Euclidean Algorithm)을 이용하여 최소공배수와 최대공약수를 구해준다. 12345678910111213141516#include int gcd(int a,int b) { return b?gcd(b,a%b):a; } int main(){ int t,a,b,g; scanf("%d",&t); while(t--) { scanf("%d %d",&a,&b); g=gcd(a,b); printf("%d %d\n",a*b/g,g); } return 0;}Colored by Color Scriptercs
https://www.acmicpc.net/problem/1939 정답(최대 중량제한)의 범위를 이분 탐색으로 줄여나가면서 최종 정답을 찾는다. BFS를 이용하여 답으로 정한 중량제한으로 시작점에서 도착점으로 갈 수 있는지 확인한다. 갈 수 있다면 범위를 올리면서 최대치를 찾고 갈 수 없다면 범위를 내린다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include #include using namespace std; vector a[100001];int n,m,u,v,w,s,e; bool bfs(int w){ queue q; vector vis..
https://www.acmicpc.net/problem/1941 C(25,7)=480700가지의 모든 경우를 만들고 BFS로 7명이 인접해 있고 S가 4명 이상인지 확인한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include #include #include using namespace std; char map[5][6];bool visit[5][5];int ans,dx[4]={0,0,-1,1},dy[4]={-1,1,0,0}; bool bfs(int sx,int sy){ int cnt=0,s=0; bool check[5]..
https://www.acmicpc.net/problem/14716 DFS나 BFS를 이용하여 연결 요소(Connected Component)의 개수를 세준다. 1234567891011121314151617181920212223242526#include int m,n,map[250][250],ans;int dx[8]={-1,-1,-1,0,0,1,1,1};int dy[8]={-1,0,1,-1,1,-1,0,1}; void dfs(int x,int y){ map[x][y]=0; for(int i=0;i
https://www.acmicpc.net/problem/1213 팰린드롬(Palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 예를 들면 abba, abbba, abcdcba 등이 팰린드롬이다. 이 문제는 문자열이 주어지고 적절히 위치를 바꿔서 팰린드롬을 만들 수 있는지 확인하는 문제이다. 1. 길이가 짝수이면 모든 알파벳의 개수도 짝수여야 한다.2. 길이가 홀수이면 하나의 알파벳의 개수만 홀수여야 한다. 위의 조건을 만족하는지 확인하고 팰린드롬을 만들 수 있다면 사전 순으로 출력한다. 먼저 A~Z까지 순서대로 보면서 개수의 절반씩 출력하고 다시 거꾸로 Z~A까지 보면서 나머지 절반을 출력하면 사전 순이 됨을 알 수 있다. 길이가 홀수인 경우는 미리 해당 인덱스를 저장한 후..
https://www.acmicpc.net/problem/7507 그리디(Greedy) 알고리즘으로 해결할 수 있다. 경기가 빨리 끝나는 순으로 하나씩 본다면 최적해가 보장됨을 알 수 있다. 1234567891011121314151617181920212223242526#include #include using namespace std; struct G { int d,s,e; };G g[50000];int n,m;bool cmp(G &g1,G &g2) { return g1.d!=g2.d?g1.d