https://algospot.com/judge/problem/read/FENCE algospot.com :: FENCE 울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체 algospot.com 각각의 높이가 다른 울타리에서 최대 넓이의 직사각형을 찾는 문제이다. 여러 방법으로 풀 수 있지만 여기서는 분할 정복으로 풀어보도록 하자. 전체 판자를 절반으로 나눈다고 하자. 그러면 우리가 찾는 최대 직사각형은 다음 세 가지 중 하나에 속한다. 1. 가장 큰 직사각형을 왼쪽 부분 문제에서만 잘라낼 수 있다. 2. 가장 큰 직사각형을 오른쪽 부분 문제에서만 잘라낼 수 있다. 3..
https://algospot.com/judge/problem/read/QUADTREE algospot.com :: QUADTREE 쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적 algospot.com 문자열을 가리키는 포인터를 하나씩 뒤로 옮겨가면서 재귀호출한다. 분할한 부분의 전체가 흰색이거나 검은색일 경우 뒤집어도 똑같은 패턴이므로 그대로 리턴한다. 그게 아니라면 다시 분할한다. 위와 아래 조각들이 바뀐 패턴이 최종 결과이다. #include #include using namespace std; string reverse(string::itera..
https://algospot.com/judge/problem/read/CLOCKSYNC algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 algospot.com 각각의 스위치들과 연결된 시계가 있다. 스위치를 누를때마다 시간이 3시간 흐른다. (12->3->6->9) 이 때 모든 시계를 12시로 돌리기 위해 스위치를 최소 몇 번 눌러야 할지 계산해야한다. 먼저 스위치를 4번 누르면 다시 원상태로 돌아온다. 그러므로 스위치를 안 누르거나 최대 3번 누르는 것으로 한정시킬 수 있다..
BOARDCOVER
https://algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 algospot.com 완전탐색 문제이다. 그런데 경우의 수를 어떻게 중복없이 체계적으로 셀 수 있을까? 순서를 강제하면 된다. 게임판의 빈 부분을 좌상단부터 하나씩 채워나간다. 이 때 모든 빈 부분이 덮어지면 경우의 수를 하나 더해준다. 아래 그림에서 별표 부분을 덮는다고 가정하자. 이 때 별표 왼쪽 부분까지는 다 채워져 있다. 그러면 L자 모양의 블록을 덮는 경우가 4가..
https://algospot.com/judge/problem/read/BOGGLE algospot.com :: BOGGLE 보글 게임 문제 정보 문제 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 algospot.com cache[x][y][idx]를 이용해서 현재 위치 (x,y)에서 idx까지 탐색했을 때 중복 탐색 여부를 확인해준다. 그러면 탐색 가지수를 줄일 수 있다. #include #include int t,n,len; char map[7][7],s[15]; int cache[5][5][10]; int dx[8]={-1,-1,-1,0,0,1,1,1}; int dy[8]..
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