https://www.acmicpc.net/problem/15789 일단 한솔 왕국이 포함된 동맹국들을 제외하고 CTP 왕국을 포함한 동맹국들과 나머지 동맹국 덩어리 중에 가장 큰 K개를 포함시킨다. DFS를 이용했다. 12345678910111213141516171819202122232425262728293031323334#include #include #include using namespace std; int n,m,x,y,c,h,k,l,v[100001],cnt,ans;vector a[100001],b; void dfs(int x){ v[x]=1,cnt++; for(auto i : a[x]) if(!v[i]) dfs(i);} int main(){ scanf("%d %d",&n,&m); while(m..
https://algospot.com/judge/problem/read/FESTIVAL 최소 L일, 최대 N일의 연속 되는 구간의 평균 비용의 최소값을 찾는다. 누적합을 미리 구해서 계산했다. 123456789101112131415161718192021#include #include using namespace std; int c,n,l,a[1001]; int main(){ scanf("%d",&c); while(c--) { double ans=100; scanf("%d %d",&n,&l); for(int i=1;i
https://www.acmicpc.net/problem/11497 인접한 통나무의 높이의 차가 최소가 되려면 어떻게 해야 할까? 처음에는 정렬하는 방법을 생각했다. 그러나 통나무가 원형으로 연결되어 있으므로 정렬할 경우 맨 앞과 맨 뒤의 차이가 최대가 되어버려서 최악의 경우가 된다. 일단 정렬을 한 후 차례대로 앞, 뒤에 쌓아가면서 정규분포처럼 만들면 높이의 차를 최소로 만들 수 있다. 12345678910111213141516171819202122232425262728#include #include using namespace std; int t,n,f,r,a[10000],b[10001],ans; int main(){ scanf("%d",&t); while(t--) { scanf("%d",&n); f..
https://www.acmicpc.net/problem/10219 처음에는 고기를 하나 하나씩 뒤집어서 안 겹치게끔 하는 방법을 생각했는데 복잡했다. 알고 보니 고기 불판 전체를 뒤집으면 되는 간단한 문제였다. 1234567891011121314151617181920#include int main(){ int t,h,w; char s[12]; scanf("%d",&t); while(t--) { scanf("%d %d",&h,&w); while(h--) { scanf("%s",s); for(int i=w-1;i>=0;i--) printf("%c",s[i]); printf("\n"); } } return 0;}cs
https://www.acmicpc.net/problem/11502 에라토스테네스의 체로 소수를 미리 구한 후 각각의 수를 세 개의 소수의 합으로 나타낼 수 있는지 확인한다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include using namespace std; int t,k,n,f,c[1000];vector p; int main(){ for(int i=2;i
https://www.acmicpc.net/problem/15654 1234567891011121314151617181920212223242526272829303132333435#include #include #include using namespace std; int n,m,a[8],c[10001];vector v; void go(){ if(v.size()==m) { for(auto i : v) printf("%d ",i); printf("\n"); return; } for(int i=0;i
https://www.acmicpc.net/problem/15649 백트래킹으로 순열을 만들어 보자. 12345678910111213141516171819202122232425262728293031#include #include using namespace std; int n,m,c[9];vector v; void go(){ if(v.size()==m) { for(auto i : v) printf("%d ",i); printf("\n"); return; } for(int i=1;i
https://www.acmicpc.net/problem/3067 d[i] = 주어진 동전으로 i원을 만드는 경우의 수 오름차순으로 주어진 동전의 경우의 수를 차례대로 추가해가면 중복없이 테이블을 채울 수 있다. 1234567891011121314151617181920212223#include #include int t,n,m,a[20],d[10001]; int main(){ scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;i
https://www.acmicpc.net/problem/15685 드래곤 커브가 세대를 거듭할수록 이전 세대의 드래곤 커브에서 왼쪽으로 90도 회전한 것이 추가된다. 이 때 규칙을 발견할 수 있다. 처음 시작점부터의 방향을 저장해 나간다. 다음 세대의 드래곤 커브는 지금까지 저장한 방향을 역순으로 보면서 방향 전환하고 왼쪽으로 90도 회전한 방향을 추가하면 된다. 모든 드래곤 커브를 맵에 표시한 후 맵 전체를 살펴본다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include using namespace std; int n,x,y,d,g,s,map[105][105],ans;int ..