백준 1074번:Z

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

1074번: Z

 

하아ㅏㅏㅏ

이 문제 처음 풀 때 전에 풀었던 문제들 때문인지 문제도 제대로 읽지 않고 모든 위치를 탐색하고 값을 저장하려는 멍청한 짓을 했다. 당연히 런타임에러도 뜨고 시간초과는 당연지사였다. (다시는 습관처럼 안풀 것이다...)

그래서 결국 이 문제는 모든 곳을 다 탐색하는 게 아니다. z라는 거에 의식을 할 필요도 없고 중요한 것은 1,2,3,4분면 위치에 내가 찾는 행과 열이 있는지 탐색해 가면 되는 것이다. 

그림을 보자

탐색할때 1사분면이나 2사분면에 없으면 그 크기에 준하는 값을 더하면 된다.(이유는 어차피 1씩증가하고 순서도 정해져 있으므로 2사분면으로 갈때는 1사분면 크기만큼 값이 증가한채로 시작한다.) 

이제 코드를 보자 코드를 보면 이해가 될듯

#include <iostream>

using namespace std;

int n, r, c;
int ans;

void search(int x, int y, int size)     //내가 찾는 행과 열 탐색하는 함수
{
    if (y == r && x == c)
    {
        cout << ans << '\n';
        return;
    }
    if (r < y + size && r >= y && c < x + size && c >= x) //현재 size에 해당하는 크기에 내가 원하는 행과열 있다면
    {
        search(y, x, size / 2);                        //1사분면 탐색
        search(y, x + size / 2, size / 2);             //2사분면 탐색
        search(y + size / 2, x, size / 2);             //3사분면 탐색
        search(y + size / 2, x + size / 2, size / 2);  //4사분면 탐색
    }
    else                          //없으면 크기 값 더하기
    {
        ans += size * size;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> r >> c;
    search(0, 0, (1 << n));
    return 0;
}