1074 - Z

• 난이도: 실버 1
• 날짜: 2023년 2월 17일
• 상태: Correct
• 추가 검토 여부: No
• 알고리즘 : 분할정복

solution

• 입력되는 배열은 행 또는 열의 크기가 $2^n$인 정사각형 형태의 배열이다. 이를 4개의 구역으로 나누는 방식을 재귀적으로 적용하였다.
• 4개로 나눠진 각각의 구역은 다시 4개의 서로 다른 구역으로 나눌 수 있다. 이 과정을 2*2배열까지 적용한다.
• 이 문제의 입력을 배열로 구현하면 메모리 초과의 발생이 자명하다. 이에 실제로 배열을 구현하지는 않고 배열의 인덱스를 나타내는 변수 idx를 이용한다.
• idx는 r행 c열에 위치한 수가 몇 번째로 출력되는지 순서를 나타낸다.
• 앞서 설명한 4개의 구역을 임의로 1섹터, 2섹터, 3섹터, 4섹터로 분류한다. 1섹터는 $2^{n-1} * 2^{n-1}$개의 칸을 을 0번, 2섹터는 1번, 3섹터는 2번, 4섹터는 3번 통과한 후 해당 섹터의 프레임에 도달한다. 이 값을 섹터의 프레임이 1이 될때까지 재귀적으로 반복한다.
• 설명이 어려운 것에 비해 코드로 구현한 것은 아래처럼 매우 간단하다.

code

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

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

    int div;
    int idx = 0;
    for(int i = 1; i <= N; i++)
    {
        div = pow(2, N-i);
        if((r/div)%2 == 0 && (c/div)%2 == 0) idx += div * div * 0;
        else if((r/div)%2 == 0 && (c/div)%2 == 1) idx += div * div * 1;
        else if((r/div)%2 == 1 && (c/div)%2 == 0) idx += div * div * 2;
        else if((r/div)%2 == 1 && (c/div)%2 == 1) idx += div * div * 3;
    }
    cout << idx << endl;

    return 0;
}

ref

1074번: Z