https://www.acmicpc.net/problem/2448 go(x,y,h)을 삼각형의 맨 위 꼭지점의 좌표, 높이로 두고 재귀 호출을 이용한 분할 정복을 한다. 12345678910111213141516171819202122232425262728293031#include char s[3100][6200]; void go(int x,int y,int h){ if(h==3) { s[x][y]=s[x+1][y-1]=s[x+1][y+1]='*'; for(int i=y-2;i
https://www.acmicpc.net/problem/1914 하노이 탑은 세 개의 기둥으로 이루어진 퍼즐이다. 첫번째 기둥에 N개의 원판들의 쌓여 있고 두 가지 규칙을 지키면서 세번째 기둥으로 옮겨야 한다. 작은 원판은 항상 큰 원판 위에 있어야 하고 한번에 하나씩만 옮길 수 있다. 이를 재귀 호출로 구현할 수 있다. go(n,x,y)를 n개의 원판을 x 기둥에서 y 기둥으로 옮기는 함수로 정의한다. 그러면 먼저 제일 아래 원판을 제외한 n-1개의 원판을 x와 y가 아닌 기둥으로 옮기고 나서 제일 아래 원판을 y로 옮긴다. 마지막으로 임시로 옮겨놓았던 n-1개의 원판을 y위에 쌓는다. 적절히 재귀 함수를 설계하면 모든 과정이 저절로 이루어짐을 알 수 있다. 이 때 점화식을 유도할 수 있다. n-1개..
https://www.acmicpc.net/problem/9020 골드바흐의 추측은 2보다 큰 모든 짝수는 두 개의 소수의 합으로 나타낼 수 있다는 것이다. 아직 정수론의 미해결 문제로 현재까지 10^18 이하에서 참이라는 것을 확인했다고 한다. 에라토스테네스의 체로 소수를 미리 구한후 n의 절반부터 줄여가면서 i와 n-i가 소수가 되는지 확인한다. 이 때 처음 발견하는 골드바흐 파티션이 두 소수의 차이가 최소이다. 123456789101112131415161718192021222324#include bool p[10001];int t,n; int main(){ p[0]=p[1]=true; for(int i=2;i*i
https://www.acmicpc.net/problem/11559 과거 뿌요뿌요라는 추억의 게임을 기억하는가? 상하좌우로 인접한 똑같은 종류의 블럭이 특정 개수가 넘으면 터지면서 콤보가 생기고 그 위의 모든 블럭들이 내려온다. 그것을 구현하는 문제이다. 매 단계마다 필드 전체를 훑으면서 DFS(Depth First Search)로 같은 블럭이 4개 이상 인접하는지 확인하고 있으면 콤보를 추가시켜주면서 다음 단계로 진행한다. dfs은 4개 이상인지 확인하는 함수이고 dfs2는 터질 블럭들을 표시하는 함수이다. 콤보가 진행된 후 해당 블럭의 열들의 모든 위의 블럭들을 내려줘야함을 유의하자. 이 동작은 move, move2에 해당한다. 더이상 콤보가 발생하지 않으면 콤보의 개수를 출력하고 종료해주면 된다. ..
https://www.acmicpc.net/problem/5635 생일의 연도, 월, 일 순으로 정렬되게끔 비교함수를 만들어 준다. 123456789101112131415161718#include #include using namespace std; struct S { char name[16]; int d,m,y; };int n;S s[100];bool cmp(S &a,S &b) { return a.y!=b.y?a.y>b.y:a.m!=b.m?a.m>b.m:a.d>b.d; } int main(){ scanf("%d",&n); for(int i=0;i
https://www.acmicpc.net/problem/3671 7자리 자연수까지의 모든 소수를 에라토스테네스의 체(Sieve of Eratosthenes)를 이용하여 미리 구하고 브루트 포스(Brute Force)로 만들 수 있는 모든 숫자를 만들어서 소수인지 확인한다. 에라토스테네스의 체는 O(NloglogN)에 1~N까지 모든 소수를 구하는 알고리즘이다. 최대 7자리이므로 10000000*log(log(10000000)) := 8450980+ 모든 경우에 대하여이므로 대략 1억번의 연산이 넘지 않음을 알 수 있기에 시간 내에 해결할 수 있음을 알 수 있다. 123456789101112131415161718192021222324252627282930313233343536#include #includ..
https://www.acmicpc.net/problem/1956 d[i][i]는 처음에 INF이므로 플로이드를 돌린 후 d[i][i]가 갱신이 되었다면 i에서 출발해서 어딘가를 돌아서 i로 다시 왔다는 의미이다. 즉, 사이클이 존재한다는 뜻이다. 갱신이 한번도 되지 않았다면 -1, 갱신이 되었다면 그 중 최소값을 출력해주면 된다. 12345678910111213141516171819202122#include #include #define INF 987654321using namespace std; int i,j,k,n,m,a,b,c,d[400][400],ans=INF; int main(){ scanf("%d %d",&n,&m); for(i=0;i
https://www.acmicpc.net/problem/1507 이미 최단 거리가 주어졌기 때문에 다시 최단 거리를 계산할 때 갱신이 발생한다면 모순이므로 -1을 출력한다. i->j 거리와 i->k->j 거리가 같다면 i->j 간선은 필요가 없으므로 제외시켜준다. 1234567891011121314151617181920212223242526272829303132#include int n,d[20][20],c[20][20],ans; int main(){ scanf("%d",&n); for(int i=0;i
https://www.acmicpc.net/problem/2357 최소값과 최대값 각각에 대하여 세그먼트 트리를 만들어 준다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include using namespace std; int n,m,a[100001],maxt[400000],mint[400000]; void max_init(int node,int start,int end){ if(start==end) maxt[node]=a[start]; else { max_init(node*2,start,(start+end)/2)..