mintuchel mintuchel

우선 방문 번호가 함수 호출 순서라는 것을 알 수 있다. 몇 번째 재귀에 해당 칸을 방문하는지가 해당 칸 번호라는 것이다 따라서 해당 방식으로(여기서는 Z) 재귀가 진행되도록 하면 된다. 그럼 일단 재귀 문을 간략하게 다음과 같이 짤 수 있다. void solve(int y, int x, int size){ size /= 2; // Z방식으로 탐색 solve(y, x, size); solve(y, x+size, size); solve(y+size, x, size); solve(y+size, x+size, size); } 그럼 이제 r c를 만나면 끝나도록 할 수 있는데 초반에 시간초과가 떴다. 이유는 찾고 남은 solve가 있으면 해당 solve들도 다 돌고 끝나기 때문 1번의 예시를 들면 다음과 같다 ..

이분탐색 풀다 완탐 풀고 싶어서 오랜만에 완탐 문제 풀어봄 그냥 한 정사각형 색종이가 만들어질때까지만 재귀를 돌려주면 된다 #include using namespace std; int** board; int white, blue; bool check(int starty, int startx, int size) { int flag; if (board[starty][startx] == 1) flag = 1; // blue else flag = 0; // white for (int y = starty; y < starty + size; y++) { for (int x = startx; x < startx + size; x++) { // 파란색인데 흰색 나오거나 if (flag && board[y][x] == ..

슬라이딩 윈도우 문제이다 보통 전체 원소 개수 N 탐색 범위 M이라고 하면 총 O(N*M)이 걸리는데 이걸 줄일 수 있다 일단 슬라이딩 윈도우의 특징은 한번 검사할때 범위가 M이라고 하면 다음 턴에는 총 두 개의 원소만 바뀐다는 것이다 맨 앞에꺼가 삭제되고 맨 뒤+1인 원소만 추가된다는 것이다 즉 맨 앞에꺼 뺀 M-1개의 원소는 그대로인 것이다 이런 dp스러운 성질을 이용해서 O(N)으로 줄일 수 있다 dp스럽다는게 굳이 매 경우마다 이미 계산한 저 두 개 사이에 있는 원소를 계산하지 않아도 된다는 것이다 여기서 보면 구간이 5이므로 총 전꺼랑 다음꺼랑 총 4개가 겹치는거다 이 그림에서는 3 2 6 -1이 겹치는거임 이건 그럼 이미 전에 계산한건데 또 계산할 필요가 없음 그래서 dp 같다는거임 dp가 그..

재귀 + dp문제 풀고 난 뒤면 정말 쉬워보이는데 생각했던 것보다 오래걸림 ㄷㄷ dp쓸 생각을 하지 못하고 모든 경우에 다 재귀로 돌려버렸기 때문이다 #include using namespace std; int N; long long X; long long ans = 0; long long total[51], patty[51]; // 1 5 1 5 1 = 13 -> mid = 7 // 1 13 1 13 1 = 29 -> mid = 15 // 1 29 1 29 1 = 61 -> mid = 31 void solve(long long start, long long end, int level) { // level1 버거일때가 종료조건 if (level == 1) { if (X - start >= 3) ans +..

항상 정사각형으로 나눠지고 크기가 1만 아니면 무조건 9개 3x3형태로 나누므로 00 03 06 30 33 36 60 63 66 이렇게 각 종이의 시작점으로 구별하고 위 점들에 대해 또 다시 재귀적으로 solve를 해주면 된다 한개의 종이가 될 수 있는지는 브루트포스로 직접 다 확인하는 수 밖에 없는듯 어차피 N

아래 코드의 결과는 시간초과이다 이유는 재귀로 풀어서 그렇다 그래도 종만북 스타일의 재귀로 해결했으므로 기록해놓는다 여기서 봐야할 것은 구현방식과 재귀호출의 과정이다 1. 타일 모양을 3차원 배열로 표현 int tile[4][3][2] = { { {0,0}, {1,0}, {1,1} }, { {0,0}, {1,0}, {0,1} }, { {0,0}, {0,1}, {1,1} }, { {0,0}, {1,0}, {1,-1} } }; 타일이 총 4종류 이므로 4층짜리 한 타일은 세 블럭이고 각각 x y 좌표가 있으므로 한 층에 3x2 배열을 배치한다. 예를 들어 첫번째 타일을 특정 좌표 x y에 배치하면 (x + 0 ,y + 0) (x + 1, y) (x + 1, y + 1) 을 타일이 차지하게 된다는 것이다 따라..