문제

백준 1074번 문제 - Z

코드

#include <bits/stdc++.h>

using namespace std;

int N, r, c;

int main()
{
    cin >> N >> r >> c;

    long long answer = 0;

    while (N != 1)
    {
        answer = answer + pow(2, 2 * N - 1) * (r / (int)pow(2, N - 1));
        answer = answer + pow(2, 2 * N - 2) * (c / (int)pow(2, N - 1));

        r = r % (int)pow(2, N - 1);
        c = c % (int)pow(2, N - 1);

        N--;
    }

    answer = answer + 2 * r + c;

    cout << answer;

    return 0;
}

풀이

원래는 재귀를 이용해 분할정복해서 푸는 문제이다.

하지만 나는 재귀를 아직까지 잘 쓰지 못한다. 그래서 땡깡을 부려 다른 방법으로 풀려했다(근데 그냥 저 코드 재귀로 옮길 수 있을 것 같은데)

일단 2차원 배열로는 절대 못푼다. 2^15 * 2^15 이니까 메모리 부족날듯

그래서 N이 1일때, 2일때, 3일때, ... 를 분석해봤다

2^N * 2^N 배열이 있을 때 이거를 4등분하고 각 등분 배열의 시작점의 위치를 살펴봤다

예를 들면 N = 2에서 배열을 4등분하면 0으로 시작하는 배열 / 4로 시작하는 배열 / 8로 시작하는 배열 / 12로 시작하는 배열로 나뉜다

그리고 우리는 행과 열을 알고 있으니까 (r, c)가 몇 번째 배열에 있는 지 추측할 수 있다

r과 c를 2^(N-1)로 나눠서 몇 번째 배열인지 확인한다

N = 2, r = 3, c = 1일 때
4등분했을때 3 / 2, 1 / 2 = 왼쪽 아래 배열에 위치해있다

이제 왼쪽 아래 배열의 시작 숫자는 규칙을 찾아보니까
행이 증가할 때는 2^(2n - 1), 열이 증가할 때는 2^(2n - 2)씩 증가하는 것을 확인할 수 있었다
시작 위치를 확인했으면 (r, c)가 새로운 배열에서 몇 번째 행과 열에 위치해있는지 업데이트 해준다

마지막으로 N이 1이되어서 반복문을 빠져나오면 2*2 배열에서 몇 번째에 위치하는지만 찾아주면 끝

역시 재귀를 마스터하는게 맞는 것 같다,,