[PS 백준 - 4.4] 1074번: Z

문제 정보

백준 1074번 - 바로가기

• 난이도: 실버 1
• 알고리즘: 분할 정복

---

코멘트

이 문제는 숫자들의 규칙성을 파악하는 것이 관건이였다.

먼저 가로 칸들을 보면 1칸 단위로 1만큼, 2칸 단위로 4만큼, 4칸 단위로 16만큼, 8칸 단위로 64만큼 증가한다. 따라서 아래와 같은 식이 성립한다.

가로 $n$칸 단위로 $4^{ \log_{2} n } = n^2$ 만큼 증가한다.

세로 칸들을 보면 1칸 단위로 2만큼, 2칸 단위로 8만큼, 4칸 단위로 32만큼, 8칸 단위로 128만큼 증가한다. 따라서 아래와 같은 식이 성립한다.

세로 $n$칸 단위로 $2 \times 4^{ \log_{2} n } = 2n^2$ 만큼 증가한다.

위 공식들을 활용하여 r행 c열부터 시작점까지 이동시키고, 그 때까지 더해진 결과들을 출력하면 된다.

1. 분할 정복 함수는 r행을 이동시키는 함수(2)와 c열을 이동시키는 함수(1) 2가지를 선언하였다.
2. c열 이동 함수의 base case는 c가 0, 1일때이다. c가 1 초과의 숫자라면 결과에 $4^{ \log_{2} n }=n^2$ 를 증가시키고, c에서 해당 칸 수를 빼준다. 그리고 맵의 크기도 반으로 줄여서 함수를 재귀호출한다.
3. r행 이동 함수의 base case는 r이 0, 1일때이다. r이 1 초과의 숫자라면 결과에 $2 \times 4^{ \log_{2} n }=2n^2$ 를 증가시키고, r에서 해당 칸 수를 빼준다. 그리고 맵의 크기도 반으로 줄여서 함수를 재귀호출한다.

---

소스 코드

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

double log_b(int x, int base) {
    return log(x) / log(base);
}

void divideConquer1(int n, int r, int c, int* result) {
    if (c == 0) return;
    if (c == 1) { *result += 1; return; }

    *result += pow(4, (int)log_b(c, 2)); // == c*c

    divideConquer1(n / 2, r, c - pow(2, (int)log_b(c, 2)), result); // == c - sqrt(c)
}

void divideConquer2(int n, int r, int c, int* result) {
    if (r == 0) return;
    if (r == 1) { *result += 2; return; }

    *result += 2 * pow(4, (int)log_b(r, 2)); // == 2*r*r

    divideConquer2(n / 2, r - pow(2, (int)log_b(r, 2)), c, result); // == r - sqrt(r)
}

int main() {
    int n, r, c;
    int result = 0;
    cin >> n >> r >> c;

    divideConquer1(n, r, c, &result);
    divideConquer2(n, r, c, &result);

    cout << result;

}