백준 1074번 : Z

문제 링크 : https://www.acmicpc.net/problem/1074

1074번: Z

 문제 설명 

1	2	5	6
3	4	7	8
9	10	13	14
11	12	15	16

이렇게 배열이있으면 번호 순서대로 Z를 그리며 숫자가 입력된다 작게 Z 그다음에 크게 Z ..

 

 알고리즘 

분할 정복으로 풀었다 

1. 재귀함수를 부를때 좌측상단 -> 우측 상단-> 좌측하단-> 우측하단 순서로 계속재귀호출

2.  num이 2가되었을 때 r,c 를 탐색하였다.

 

 

코드

#include<iostream>
#include <cmath> //pow();
using namespace std;
 
int N, r, c;
int result = 0;
 
void func(int n, int y, int x) {
    if (n == 2) {
        for (int i = y; i < y + n; i++) {
            for (int j = x; j < x + n; j++) {
 
 
                if (i == r && j == c) {
                    cout << result;
                    return;
                }
                result++;
            }
        }
        return;
    }
    else {
        func(n / 2, y, x);// 좌측상단
        func(n / 2, y, x + n / 2); //우측상단
        func(n / 2, y + n / 2, x);//좌측하단
        func(n / 2, y + n / 2, x + n / 2);//우측 하단
        return;
    }
}
int main() {
    cin >> N >> r >> c;
 
    func(pow(2, N), 0, 0);
 
}