https://www.acmicpc.net/problem/1074
1074번: Z
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을
www.acmicpc.net
이 문제는 앞으로 보나 뒤로 보나 분할 정복을 쓸거 같은 문제였다 처음에는 배열의 값을 분할정복을 이용해서 넣어주려했으나 이문제의 배열만큼의 크기를 선언하려면은 이문제의 메모리 제한을 넘는 배열이 생성 된다 이에 이문제는 소속 해 있는 행과 렬을 계산 해주면서 푸는 문제가 되겠다.
#include <iostream>
#include <cmath>
using namespace std;
int n, r, c;
int ans;
void solution(int row , int col , int size) {
if (r == row && c == col) {
cout << ans;
return;
}
if (r >= row && r < row + size && c >= col && c < col +size)
{
solution(row, col, size / 2);//1사분면
solution(row, col + size/2, size / 2); //2사분면
solution(row + size/2, col, size / 2); // 3사분면
solution(row + size / 2, col + size / 2, size / 2); //4사분면
}
else {
ans += size * size;
}
}
int main() {
cin >> n >> r >> c;
solution(0, 0, pow(2,n));
}이 문제의 설명을 하자면
일단 초기값을 입력 받았을때 size의 크기의 col이 0~7 row가 0~7에 있는지 확인한다 그후 n과 r이 있는 사분면을 만났을 때 그 4분면을 4개로 쪼갠후 자신의 값이 포함되어 있는 4분면 쪽으로 들어가 답이 나올 때 까지 쪼개면서 결국에는 size가 1이 될 때까지 4분면의 4분면...을 찾아 들어간다 만약 4분면에 포함이 안되면 그 4분면의 크기만큼 ans값에 더해준다. 왜냐면 그만큼의 크기를 뛰어넘은것으로 생각되기 때문이다
이에 이렇게 풀면 분할정복으로 이문제를 풀 수 있다