BOJ : 1074 Z

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

기초 분할 정복 문제

재귀를 구현할 머리가 안되는지 완전 탐색이나 DP보다 이게 더 어렵게 느껴질 때가 많다.

다행히 2^N꼴이기 때문에 쉽게 접근이 가능하다.

n==2, 2*2의 제일 작은 사각형이 될 때까지 4등분으로 나누어주고 (line. 31~34) Z모양으로 cnt를 차례대로 증가시켜주자.

#include <stdio.h>
#include <math.h>
int N,R,C,cnt=0;
void dnc(int n,int r,int c){
    if(n==2){
        if(r==R && c==C) {
            printf("%d\n",cnt++);
            return ;
        }
        cnt++;
        
        if(r==R && c+1==C) {
            printf("%d\n",cnt++);
            return ;
        }
        cnt++;
        
        if(r+1==R && c==C) {
            printf("%d\n",cnt++);
            return ;
        }
        cnt++;
        
        if(r+1==R && c+1==C) {
            printf("%d\n",cnt++);
            return ;
        }
        cnt++;
        return;
    }
    dnc(n/2, r, c);
    dnc(n/2, r, c+n/2);
    dnc(n/2, r+n/2, c);
    dnc(n/2, r+n/2, c+n/2);
}
int main(){
    scanf("%d%d%d",&N,&R,&C);
    dnc(pow(2,N), 0, 0);
}