1780 - 종이의 개수

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

Solution

• 혹시나 하는 마음에 chat GPT에게 문제를 그대로 주었다
• 한번에 정답을 맞췄다... 충격적이다.

code

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<vector<int>> paper;

bool is_all_same(int x, int y, int size) {
    for (int i = x; i < x + size; i++) {
        for (int j = y; j < y + size; j++) {
            if (paper[x][y] != paper[i][j]) {
                return false;
            }
        }
    }
    return true;
}

void count_paper(int x, int y, int size, vector<int>& count) {
    if (is_all_same(x, y, size)) {
        count[paper[x][y] + 1]++;
    } else {
        int next_size = size / 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                count_paper(x + i * next_size, y + j * next_size, next_size, count);
            }
        }
    }
}

int main() {
    cin >> N;
    paper.resize(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> paper[i][j];
        }
    }

    vector<int> count(3);
    count_paper(0, 0, N, count);
    for (int c : count) {
        cout << c << '\n';
    }

    return 0;
}

ref

1780번: 종이의 개수