본문 바로가기

Beakjoon/divide & conquer

 (5)
[백준] 1074번 Z (C++) - divide & conquer 문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 코드 첫번째 시도(시간 초과) #include #include using namespace std; int n, r, c, cnt = 0; void zSearch(int y, int x, int len){ if(len==1){ if(y==r && x==c){ cout > r >> c; int len = pow(2, n); zSearch(0,0,len); return 0; } 정답 #..
[백준] 1992번 쿼드트리 (C++) - divide & conquer 문제 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 코드 #include #include using namespace std; int picture[64][64]; void compression(int y, int x, int n){ bool flag = true; int check = picture[y][x]; for(int i=y; i
[백준] 2447번 별 찍기 - 10 (C++) - divide & conquer 문제 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 코드 내 풀이 #include using namespace std; int paper[6561][6561]; void star(int y, int x, int n){ if(n == 0){ return; } // 가운데 별 제외 int d = n/3; for(int i=y+d; i
[백준] 1780번 종이의 개수 (C++) - divide & conquer 문제 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 코드 #include using namespace std; int n; int paper[2187][2187]; int cnt[3]; void divide(int y, int x, int n){ int num = paper[y][x]; int flag = true; for(int i=y; i
[백준] 2630번 색종이 만들기 (C++) - divide & conquer 문제 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 코드 #include using namespace std; int paper[128][128]; int white = 0; int blue = 0; void cutPaper(int y, int x, int size){ bool flag = false; int check = paper[y][x]; for(int i=y; i < y+size; i++){ for(int ..

티스토리툴바