[C++] BAEKJOON 1074 Z

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

1074번: Z

분할정복 을 사용하여 문제를 해결하였습니다.

기존에 하던 방식과 마찬가지로 2차원 배열을 선언하고 배열의 값을 전부 채운 후, 마지막에 인덱스를 통해서 원하는 위치의 값을 찾아주었습니다. 하지만 결과는 너무 큰 2차원 배열을 선언했기 때문에 메모리 초과 로 틀렸습니다.

#include <iostream>

using namespace std;

int board[16400][16400];

int pow(int n){
    int result = 1;
    for (int i=0;i<n;i++){
        result = result * 2;
    }
    return result;
}

int value = 0;
void solve(int y, int x, int N){
    if (N==2){
        for (int i=0;i<2;i++){
            for (int j=0;j<2;j++){
                board[y+i][x+j] = value++;
            }
        }
        return;
    }
    
    int M = N/2;
    
    for (int i=0;i<2;i++){
        for (int j=0;j<2;j++){
            solve(y+M*i,x+M*j,N/2);
        }
    }
}

int main(int argc, const char * argv[]) {
    
    int N, r,c;
    cin >> N >> r >> c;

    solve(0,0,pow(N));
    
    cout << board[r][c];
    
    return 0;
}

 

따라서 전체 값을 저장할 2차원 배열을 선언하지 않고 문제를 해결해야 합니다. 현재 상태에서 4개의 구역으로 나누었을 때 원하는 좌표가 부분 구역에 없을 경우, 그 구역을 굳이 재귀적으로 접근하지 않고 크기만큼 더해주고 건너뛰게 됩니다.

#include <iostream>

using namespace std;

int r,c;

int pow(int n){
    int result = 1;
    for (int i=0;i<n;i++){
        result = result * 2;
    }
    return result;
}

int value = 0;
void solve(int y, int x, int N){
    if (y==r && x==c) {
        cout << value << "\n";
        return;
    }
    
    else if (N==1) value++;
    else if (!(y<=r && r<y+N && x<=c && c<x+N)){
        value += N*N;
        return;
    }
    
    int M = N/2;
    
    for (int i=0;i<2;i++){
        for (int j=0;j<2;j++){
            solve(y+M*i,x+M*j,N/2);
        }
    }
}

int main(int argc, const char * argv[]) {
    
    int N;
    cin >> N >> r >> c;

    solve(0,0,pow(N));
    
    return 0;
}