백준 17829 222-풀링 / C++

문제 : 17829

풀이 point

행렬을 4분면씩 계속해서 나눈후 $2*2$ 행렬에서 두번째로 큰 수를 뽑는다. 뽑은 수들로 만든 행렬에서 또 $2*2$행렬로 나눈 후 두번째로 큰 수를 찾아낸다. 계속해서 반복한 후 마지막으로 남은 수를 출력한다.

풀이 방법

재귀를 통해 나눈다. 값을 저장하는 크기 4의 배열이 필요하다. x, y(좌표)의 위치를 통해 어느 사분면의 위치하는지를 파악한 후 재귀를 한다.

1사분면 -> x, y
2사분면 -> x, y+half
3사분면 -> x+half, y
4사분면 -> x+half, y+half

코드

#include <iostream>
#include <algorithm>

int N;
int grid[1024][1024];

int recur(int k, int x, int y) {
    if (k == 2) {
        int arr[4] = {grid[x][y], grid[x][y + 1], grid[x + 1][y], grid[x + 1][y + 1]};
        std::sort(arr, arr + 4);
        return arr[2]; // 두 번째로 큰 값 반환
    }

    int half = k / 2;
    int values[4] = {
        recur(half, x, y),
        recur(half, x, y + half),
        recur(half, x + half, y),
        recur(half, x + half, y + half)
    };

    std::sort(values, values + 4);
    return values[2]; // 상위 4개 값 중 두 번째로 큰 값 반환
}

int main() {
    std::cin >> N;

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            std::cin >> grid[i][j];
        }
    }

    std::cout << recur(N, 0, 0) << '\n';

    return 0;
}