https://www.acmicpc.net/problem/1654 이분 탐색으로 정답의 범위를 줄여가면서 랜선의 최대 길이를 찾는다. 랜선의 개수가 모자라면 범위를 내리면서 개수를 늘려가고 랜선의 개수가 원하는 개수보다 같거나 크다면 범위를 최대한 올려가면서 랜선의 최대 길이를 찾는다. 이 때 mid가 정답이 되는 것이 아니라 매번 조건을 만족하는지 확인하면서 정답을 갱신해줘야 한다. 12345678910111213141516171819202122232425262728293031323334#include long long k,n,ans,lc[10000],max; void bs(){ long long left=1,right=max,mid; while(left
https://www.acmicpc.net/problem/1021 덱(Double Ended Queue)을 이용한 구현 문제이다. 매 단계마다 왼쪽으로 밀면서 빼는것과 오른쪽으로 밀면서 빼는 것 중에 연산을 더 적게 쓰는 것을 사용한다. 구현할 때 index 범위와 사용에 주의하자. 헷갈리지 않게 index 시작을 0으로 다 맞춰주는 것도 한 방법이다. 1234567891011121314151617181920212223242526272829303132333435363738#include #include using namespace std; int main(){ int n,m,t,cnt=0; scanf("%d %d",&n,&m); deque dq(n); for(int i=0;i
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