(C++) - 백준(BOJ) 1074번 : Z 답

www.acmicpc.net/problem/1074

1074번: Z

재귀를 이용해 풀었습니다(백트레킹 방식.)

 

풀이방법 :

 일반적인 정적 배열 할당으로는 풀 수가 없습니다. 최대 배열 크기 2^15 x 2^15 개 = 20억 이상. 따라서 고려할 수 있는 것은 재귀 또는 특정 공식을 찾아 푸는 것입니다.

 

Code :

#include <iostream>
#include <cmath>
using namespace std;
int n,r,c,ans=0;
int dx[4] = {0,0,1,1};
int dy[4] = {0,1,0,1};

void fillBoard(int n,int x,int y){
    if(n==2){
        for(int i = 0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx== r && ny == c){
                cout << ans;
                return;
            }
            ans++;
        }
        return;
    }
    fillBoard(n/2,x,y);
    fillBoard(n/2,x,y+n/2);
    fillBoard(n/2,x+n/2,y);
    fillBoard(n/2,x+n/2,y+n/2);
}

int main(){
    cin >> n >> r >> c; // 2*n X 2*n의 판에서 (r,c)는 무슨 숫자?
    fillBoard(1<<n,0,0);
}