BOJ 1074 - Z / C++

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

1074번: Z

 

 

풀이

2^n x 2^n 배열을 직접 그리려하면 시간 제한에 걸려 풀 수 없다.

따라서, 배열을 2^(n-1) x 2^(n-1) x 4로 네 구역으로 나누고 차례대로 Z 모양의 순서로 방문하면 된다.

 

 

 

예를 들어, 배열이 위의 그림과 같이 있을 때 r=2, c=1에 위치한 값을 구하려고 한다.

현재 n=2이므로 2^2 x 2^2 배열이다. 이를 네 구역으로 나누면 1구역(0~3), 2구역(4~7), 3구역(8~11), 4구역(12~15)로

나눌 수 있고 r=2, c=1는 3구역에 위치한다.

 

따라서 1, 2구역은 볼 필요 없이 그 크기만큼 더해버리고 다시 3구역에서 재귀적으로 구역을 나누어 계산하면

좌표가 r=2, c=1에 도달하게 되어 그동안 더했던 값들을 return 하면 된다.

 

호출 순서가 1, 2, 3, 4구역 순서이므로 4구역은 호출되지 않는다.

 

코드

#include <iostream>
#include <cmath>
using namespace std;

int n, r, c;
int ans = 0;

//행(row)는 y와 관련, 열(column)은 x와 관련
void solution(int y, int x, int size) {
    if(y == r && x == c){
        cout << ans;
        return;
    }

    if(r < y + size && r >= y && c < x + size && c >= x){
        solution(y, x, size / 2);
        solution(y, x + size / 2, size / 2);
        solution(y + size / 2, x, size / 2);
        solution(y + size / 2, x + size / 2, size / 2);
    }
    else ans += size*size;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> r >> c;
    solution(0, 0, pow(2, n));
}