1074번

1074번 - Z

처음에는 처음부터 모든 점을 방문하면서, 찾고자 하는 r,c 가 나왔을 때 답을 출력하도록 했더니, 시간초과가 발생했다.

그래서 다 방문하지 않고, r,c를 찾아가는 코드를 분할정복과 재귀를 이용해서 구현했다.

왼쪽 상단, 오른쪽 상단, 왼쪽 하단, 오른쪽 하단 순서로 방문하도록 for문을 이용해서 첫값을 구했다.

그리고 해당하는 점이 사분할 된 곳 중에 어느 곳에 있는지 확인하고, 그 사분면으로 이동하도록 구현했다.

만약 2사분면에 있다면, 1사분면의 모든 갯수를 더한 다음 순서가 되고,

만약 3사분면에 있다면, 1사분면+ 2사분면의 모든 갯수를 더한 다음 순서가 되기 때문에

모든 정점을 방문하지 않고 , 곧바로 목표로 하는 정점으로 방문해도 정답을 구할 수 있기 때문이다.

<정답 코드>

#include<iostream>
#include<math.h>
using namespace std;
 
int n, r, c, ans, cnt = 0;
int dx[4] = { 0,0,1,1 };
int dy[4] = { 0,1,0,1 };
void dfs(int size, int x, int y,int cnt)
{
    if (x == r && y == c)
    {
        cout << cnt << "\n";
        exit(1);
    }
    
    for (int i = 0; i < 4; i++)
    {
        int nsize = size / 2;
        int nx = x + dx[i] * nsize;
        int ny = y + dy[i] * nsize;
 
        if (r >= nx && r < nx + nsize && c >= ny && c < ny + nsize)
        {
            dfs(nsize, nx, ny, cnt + (i*nsize*nsize));
        }
    }
 
 
    return;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
 
    cin >> n >> r >> c;
 
    dfs((int)pow(2,n), 0, 0,0);
 
    return 0;
}