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 ..
https://www.acmicpc.net/problem/15686 치킨집 중에서 M개를 고르는 모든 조합을 만든 후 각각의 집을 가장 가까운 치킨집에 연결시킨다. 모든 경우 중 최소값이 답이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include #include #define INF 987654321using namespace std; int n,m,t,lenh,lenc,ans=INF;vector h,c; int dist(pair a,pair b){ return abs(a.first-b.first)+abs(a.second-b.second);} int main(){..
https://www.acmicpc.net/problem/14891 K번 톱니바퀴를 회전시킨 후 점수의 합을 구하는 문제이다. 매번 톱니바퀴를 돌리면 서로 맞닿은 극이 다를 경우에만 회전하게 된다. 현재 상태를 기준으로 다음 회전할 방향을 미리 저장한 후 move함수를 이용하여 상태를 변화시킨다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091#include #include // w[i][j]: i번째 톱니바퀴의 j번째 점수// nd[i]: i번..