백준 1074 Z c++ [컴공과고씨]

https://www.acmicpc.net/problem/1074

1074번: Z

문제를 보고 분할 정복을 사용해서 풀 수 있겠다는 생각이 들었다.

일단 분할 정복 같은 경우는 큰 문제를 작은 문제로 나눠서 푸는 방법이다.

지금 같은 경우 큰 정사각형에서 크기가 4인 정사각형까지 쪼개서 풀어주면 쉽다.

 

큰 정사각형은 4분할 해서 4개의 정사각형을 만들 수 있다. 그리고 조건문을 사용해서 4분면 중  

위 순서대로 검사를 하여 구하고자하는 위치가 어디에 속해 있는지 확인해주고 그 영역에서 다시 정사각형을 4분할 해준다. 만약 2번에 속해있다고 한다면

이런 식으로 말이다.

여기서 검사하는 순서를 저렇게 해놓은 이유는 만약 1번에 없다면 1번의 size * size를 해주어 1번 끝까지의 순서를 쉽게 구할 수 있기 때문에 순서를 지켜주었다. 이런식으로 찾다보면 원하는 열과 행 위치를 찾을 수 있다. 찾으면 아까 전에 말했듯이 앞의 4분면에 속하지 않았다면 size * size를 하면서 순서를 세왔기 때문에 찾을 때 까지의 순서를 출력해주면된다. 

 

전체 코드

#include <iostream>
#include <cmath>
using namespace std;
int n, r, c;
int ans = 0;
void dc(int x, int y, int size){
    if(c==x && r==y){ // 찾으려는 열과 행이 일치하면 
        cout << ans;
        return;
    }
    else if (c < x + size && r < y + size && c >= x && r >= y){
        //찾으려는 열과 행이 4분면안에 있을 경우
        dc(x, y, size / 2);
        dc(x + size / 2, y, size / 2);
        dc(x, y + size / 2, size / 2);
        dc(x + size / 2, y + size / 2, size / 2);
    }else{ // 없다면 숫자 카운트 -> 정사각형 넓이
        ans += size * size;
    }
}
int main(){
    cin >> n >> r >> c;
    dc(0, 0, pow(2, n));
    return 0;
}

사용 문법 : 분할 정복

 

yea!