색종이 만들기

문제

색종이 만들기

풀이

함수 get_paper_count(i, j, n)을 정의합시다. 이 함수는 부터 까지 색종이의 개수를 구합니다.

만약 해당 범위가 모두 같은 색인 경우 해당 색의 종이의 개수를 늘립니다. 그렇지 않은 경우 사분면으로 쪼개서 get_paper_count를 아래와 같이 호출하면 됩니다.
(i, j, n / 2),
(i + n / 2, j, n / 2),
(i, j + n / 2, n / 2),
(i + n / 2, j + n / 2, n / 2)

코드

로 나누는 대신 오른쪽 시프트(>>) 연산자를 사용했습니다.

Python

import sys
 
input = lambda: sys.stdin.readline().rstrip()
 
 
n = int(input())
 
color = [list(map(int, input().split())) for _ in range(n)]
count = [0, 0]
 
 
def calculate_paper_count(r, c, n):
    all_equals = True
    for i in range(r, r + n):
        if not all_equals:
            break
        for j in range(c, c + n):
            if color[i][j] != color[r][c]:
                all_equals = False
                break
 
    if all_equals:
        count[color[r][c]] += 1
        return
 
    n >>= 1
    calculate_paper_count(r, c, n)
    calculate_paper_count(r + n, c, n)
    calculate_paper_count(r, c + n, n)
    calculate_paper_count(r + n, c + n, n)
 
 
calculate_paper_count(0, 0, n)
 
print(count[0], count[1], sep="\n")

C++

#include <bits/stdc++.h>
using namespace std;
 
vector<vector<int>> color;
array<int, 2> cnt;
 
void calculatePaperCount(int r, int c, int n) {
    bool allEquals = true;
 
    for (int i = r; i < r + n; i++) {
        if (not allEquals)
            break;
        for (int j = c; j < c + n; j++) {
            if (color[i][j] != color[r][c]) {
                allEquals = false;
                break;
            }
        }
    }
 
    if (allEquals) {
        cnt[color[r][c]]++;
        return;
    }
 
    n >>= 1;
    calculatePaperCount(r, c, n);
    calculatePaperCount(r + n, c, n);
    calculatePaperCount(r, c + n, n);
    calculatePaperCount(r + n, c + n, n);
}
 
int main() {
    int n;
    cin >> n;
 
    color = vector(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cin >> color[i][j];
    }
 
    calculatePaperCount(0, 0, n);
    cout << cnt[0] << '\n' << cnt[1];
}

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    static int cnt[] = new int[2];
    static int color[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
        color = new int[n][n];
 
        for (int i = 0; i < n; i++) {
            StringTokenizer tk = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++)
                color[i][j] = Integer.parseInt(tk.nextToken());
        }
 
        calculatePaperCount(0, 0, n);
 
        bw.write(cnt[0] + "\n" + cnt[1]);
        bw.close();
    }
 
    static void calculatePaperCount(int r, int c, int n) {
        boolean allEquals = true;
 
        for (int i = r; i < r + n; i++) {
            if (!allEquals)
                break;
            for (int j = c; j < c + n; j++) {
                if (color[i][j] != color[r][c]) {
                    allEquals = false;
                    break;
                }
            }
        }
 
        if (allEquals) {
            cnt[color[r][c]]++;
            return;
        }
 
        n >>= 1;
        calculatePaperCount(r, c, n);
        calculatePaperCount(r + n, c, n);
        calculatePaperCount(r, c + n, n);
        calculatePaperCount(r + n, c + n, n);
    }
}