1780)종이의 개수

문제요약

3의 제곱의 수인 n이 주어지고 n*n크기의 -1, 0, 1이 적힌 수 배열이 주어진다. 이때,
1. 종이에 쓰여진 숫자가 모두 같으면 종이를 사용한다.
2. 1을 만족하지 못하면 종이를 9등분 한다. 자른 종이들로 1을 만족할때까지 반복한다.
이 수행을 완료했을 때, 각 -1, 0, 1이 쓰여진 종이가 몇장인지 구하는 문제다.
그러니까, 사용할 수 있는 종이는 같은 숫자가 쓰여진 종이만 사용가능하므로 3^i*3^i크기의 종이에 같은 숫자가 쓰여있어야 한다.

문제 풀이

3^i*3^i크기의 종이에 하나라도 불순문(?)이 섞여 있다면 모든 종이를 9등분 해야 한다. 따라서, 재귀 함수로 9등분의 속성(-1, 0, 1로 이루어졌거나 섞어 있거나)을 구하고 모든 9등분의 속성이 같다면 해당 숫자를 리턴하거나 아니면 각 속성의 종이 갯수를 세면 된다.

코드

//
//  1780.cpp
//  algorithm_study
//
//  Created by Jihyun Kyoung on 2023/08/11
//
#include<iostream>
#include <cstdio>
using namespace std; 
short int* arr;
int* num;
int idx, ridx;
char buffer[1<<20];
int check(int a, int b, int n, int N);
static inline char read();
static inline int readint();

int main(){
    int N;
    N = readint();
    int tmp[4]={0,};
    num = &tmp[1];
    arr = new short int[N*N];
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            arr[i*N+j]=readint();
    num[check(0,0, N,N)]++;
    for(int i=-1;i<2;i++)
        cout<<num[i]<<endl;
}

static inline char read(){
    if(ridx == idx){
        ridx = fread(buffer, 1, 1<<20, stdin);
        idx = buffer[ridx] = 0;
    }
    return buffer[idx++];
}
static inline int readint() {
    int r =0;
    bool n = 0;
    char c = read();
    while(c<33) 
    c = read();
    if(c == '-')n = 1, c=read();
    while(c>=48&&c<=57){
        r = r*10+(c&15);
        c=read();
    }
    return n? -r:r;
}

int check(int a, int b, int n, int N){
    int chk_arr[9],chk_ind =0, same =1;
    if(n==1){
        return arr[a*N+b];
    }
    
    int k = n/3;
    chk_arr[0] = check(a, b, k, N); chk_arr[1] = check(a, b+k, k, N); chk_arr[2] = check(a, b+k*2, k, N);

    chk_arr[3] = check(a+k, b, k, N); chk_arr[4] = check(a+k, b+k, k, N); chk_arr[5] = check(a+k, b+k*2, k, N);

    chk_arr[6] = check(a+k*2, b, k, N); chk_arr[7] = check(a+k*2, b+k, k, N); chk_arr[8] = check(a+k*2, b+k*2, k, N);

    for(int i = 1;i<9;i++)
        if(chk_arr[0] != chk_arr[i]){
            same = 0;
            break;
        }
    if(same==1&&chk_arr[0]!=2)
        return chk_arr[0];

    for(auto& o:chk_arr){
        num[o] +=1;
    
        return 2;
    }
}

어려웠던 점

1. cin의 한계
   이 문제는 나에게 cin의 한계를 알게 해주는 문제였다. 문제를 다 풀고 나서도 몇번이고 계속 재제출 했는데 그 이유는 속도가 다른 사람들에 비해 너무 느렸기 때문이었다. 이유를 찾다보니 아무도 cin을 그대로 쓴 사람은 없었다.
   
   나는 속도가 1000대였는데 사람들은 50정도 였다.
   대부분 fread()함수를 이용하여 입력을 최대한 빠르게 받고 있었다.
2. ;과 ,의 차이
   한줄에 쓸 때는 ,로
3. inline 코드
   c++에서 제공하는 기능으로 기존 함수 호출 방식(함수를 스택에 올리고 반환 주소를 저장해서 함수로 이동했다가 돌아오는 방식) 말고 바로 함수를 치환하여 사용하도록 하여 속도를 향상시킨다. 비슷한 기능으로 c의 매크로 함수가 있다고 한다.

끝